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.

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