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"]


Calculator

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

data ExprT = Lit Inte­ger
| Mul ExprT ExprT


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

e0 = (Lit 3)
(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