Working with Abstractions

This assign­ment is due March 15 at 11:59 PM. Pull the Github repos­i­tory and start work­ing on Assign­ment2.hs. This home­work is based on that of Niki Vazou and Brent Yorgey.

Maps and Folds

We’ve seen map­ping and fold­ing on lists. Here you are required to port these pat­terns to trees. A Tree is either empty or con­tains a value and two sub­trees.

data Tree a = Nil | Node a (Tree a) (Tree a)
  deriv­ing (Eq, Show)

For test­ing, we can define few trees.

t0 = Node 1 (Node 2 Nil Nil) Nil
t1 = Node 0 t0 t0
t2 = Node "a" (Node "see" Nil Nil) (Node "tree" Nil Nil)
  1. Define a mapT func­tion that maps a func­tion over all ele­ments of a tree. Here are some exam­ples of how mapT works.

    mapT ((+) 1) t0
      == Node 2 (Node 3 Nil Nil) Nil
    mapT ((++) "!") t2
      == Node "!a" (Node "!see" Nil Nil) (Node "!tree" Nil Nil)
  2. Define a func­tion foldT that folds monoidal ele­ments of a tree, top-to-bot­tom and left-to-right. Here are some exam­ples.

    foldT t2
      == "seeatree"
    get­Sum . foldT $ mapT Sum t1
      == 6
    get­Prod­uct . foldT $ mapT Prod­uct t1
      == 0

    Here we’re using the Sum and Prod­uct con­struc­tors from Data.Monoid. These are wrap­pers over Inte­ger that deter­mine the monoidal oper­a­tion. In the case of Sum it’s +, and Prod­uct is *.

  3. Use your foldT func­tion to define a func­tion elemsT that returns the list of all the ele­ments of a tree. Note that it is fine for the result­ing list to con­tain dupli­cate ele­ments.

    elemsT t0 == [2, 1]
    elemsT t2 == ["see", "a", "tree"]


Con­sider a small cal­cu­la­tor lan­guage.

data ExprT = Lit Inte­ger
           | Add ExprT ExprT
           | Mul ExprT ExprT

For test­ing pur­poses, we will use the fol­low­ing small exam­ples.

e0 = (Lit 3)
e1 = (Add (Lit 1)
          (Lit 1))
e2 = (Add (Lit 1)
          (Mul (Lit 2)
               (Lit 2)))
  1. Write a func­tion eval that eval­u­ates an expres­sion in this lan­guage.

    eval e0 == 3
    eval e1 == 2
    eval e2 == 5
  2. Make ExprT an instance of the Show type­class.

    show e0 == "3"
    show e1 == "(1+1)"
    show e2 == "(1+(2*2))"
  3. Cre­ate the Expr type­class with the func­tions lit, add, and mul which par­al­lel the con­struc­tors of ExprT. Con­sider the fol­low­ing exam­ple.

    e = mul (add (lit 2) (lit 3)) (lit 4)

    If you ask for the type of e you’ll get Expr a => a. This means the type of e could be any Expr. We can use a type anno­ta­tion to enforce a par­tic­u­lar inter­pre­ta­tion, but that requires mak­ing some instances of Expr.

    Now make each of the fol­low­ing types an instance of Expr.

    • ExprT in the obvi­ous way.

      e :: ExprT
        == Mul (Add (Lit 2) (Lit 3)) (Lit 4)
    • Inte­ger that works like the orig­i­nal cal­cu­la­tor.

      e :: Inte­ger
        == 20
    • Bool where every lit­eral value less than or equal to 0 is inter­preted as False, and all pos­i­tive Inte­gers are inter­preted as True. Addi­tion is log­i­cal or, mul­ti­pli­ca­tion is log­i­cal and.

      e :: Bool
        == True
    • Mod7 where all arith­metic is done mod­ulo 7. Since Mod7 is really just a re-inter­pre­ta­tion of Inte­ger, we define a wrap­per with new­type.

      get­Mod7 (e :: Mod7)
        == 6