# Working with Abstractions

This assignment is due March 15 at 11:59 PM. Pull the Github repository and start working on `Assignment2.hs`

. This homework is based on that of Niki Vazou and Brent Yorgey.

## Maps and Folds

We’ve seen mapping and folding on lists. Here you are required to port these patterns to trees. A `Tree`

is either empty or contains a value and two subtrees.

data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Eq, Show)

For testing, 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)

Define a

`mapT`

function that maps a function over all elements of a tree. Here are some examples 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)

Define a function

`foldT`

that folds monoidal elements of a tree, top-to-bottom and left-to-right. Here are some examples.foldT t2 == "seeatree" getSum . foldT $ mapT Sum t1 == 6 getProduct . foldT $ mapT Product t1 == 0

Here we’re using the

`Sum`

and`Product`

constructors from`Data.Monoid`

. These are wrappers over`Integer`

that determine the monoidal operation. In the case of`Sum`

it’s`+`

, and`Product`

is`*`

.Use your

`foldT`

function to define a function`elemsT`

that returns the list of all the elements of a tree. Note that it is fine for the resulting list to contain duplicate elements.elemsT t0 == [2, 1] elemsT t2 == ["see", "a", "tree"]

## Calculator

Consider a small calculator language.

data ExprT = Lit Integer | Add ExprT ExprT | Mul ExprT ExprT

For testing purposes, we will use the following small examples.

e0 = (Lit 3) e1 = (Add (Lit 1) (Lit 1)) e2 = (Add (Lit 1) (Mul (Lit 2) (Lit 2)))

Write a function

`eval`

that evaluates an expression in this language.eval e0 == 3 eval e1 == 2 eval e2 == 5

Make

`ExprT`

an instance of the`Show`

typeclass.show e0 == "3" show e1 == "(1+1)" show e2 == "(1+(2*2))"

Create the

`Expr`

typeclass with the functions`lit`

,`add`

, and`mul`

which parallel the constructors of`ExprT`

. Consider the following example.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 annotation to enforce a particular interpretation, but that requires making some instances of`Expr`

.Now make each of the following types an instance of

`Expr`

.`ExprT`

in the obvious way.e :: ExprT == Mul (Add (Lit 2) (Lit 3)) (Lit 4)

`Integer`

that works like the original calculator.e :: Integer == 20

`Bool`

where every literal value less than or equal to`0`

is interpreted as`False`

, and all positive`Integers`

are interpreted as`True`

. Addition is logical or, multiplication is logical and.e :: Bool == True

`Mod7`

where all arithmetic is done modulo`7`

. Since`Mod7`

is really just a re-interpretation of`Integer`

, we define a wrapper with`newtype`

.getMod7 (e :: Mod7) == 6