# CSCI 312 Assignment #2

This assignment is a modified version of Professor Greenberg’s Homework #2.  As before, I’ve selected a subset of the homework that I was able to complete in a reasonable amount of time, and you should feel free to complete other exercises for extra credit.

Problem 1: arithmetic expressions

One of the objectives of this course is being able to design your own programming languages and build interpreters for them.  Our first such first language will be a simple one: arithmetic expressions using +, *, and negation.

``````data ArithExp =
Num Int
| Plus ArithExp ArithExp
| Times ArithExp ArithExp
| Neg ArithExp``````

(a)

Write a `Show` instance for `ArithExp`, which amounts to a function `show :: ArithExp -> String`. You do not need to write type signatures for functions in type class instances.

Your function should print a parseable expression, i.e., one that you could copy and paste back in to Haskell to regenerate the original term. For example, `show (Num 5)` should yield the string `"Num 5"`, while `show (Neg (Plus (Num 1) (Num 1)))` should yield the string `"Neg (Plus (Num 1) (Num 1))"`.

``````instance Show ArithExp where
show = undefined``````

(b)

Write an `Eq` instance for `ArithExp`, defining a function `(==) :: ArithExp -> ArithExp -> Bool`; use the standard “equal structures are equal” interpretation.

``````instance Eq ArithExp where
e1 == e2 = undefined``````

(c)

We’re going to write an interpreter, which takes an arithmetic expression and evaluates it to a number. The general strategy here is the same as when we wrote naturally recursive functions over lists: break down each case of the datatype definition and use recursion on subparts.

For example, `eval (Plus (Num 42) (Neg (Num 42)))` should yield `0`.

``````-- | Tests for arithmetic evaluation. Write your own!
-- >>> eval (Plus (Num 42) (Neg (Num 42)))
-- 0
eval :: ArithExp -> Int
eval = undefined``````

(d)

Let’s extend our language to support subtraction—now we’re really cooking! Note that we let Haskell derive a “parseable” show instance for us.

``````data ArithExp' =
Num' Int
| Plus' ArithExp' ArithExp'
| Sub' ArithExp' ArithExp'
| Times' ArithExp' ArithExp'
| Neg' ArithExp'
deriving Show``````

But wait: we should be able to encode subtraction using what we have, giving us a very nice evaluation function.

``````eval' :: ArithExp' -> Int
eval' = eval . translate``````

Write a function that will translate this extended language to our original language—make sure that `eval'` does the right thing.

``````translate :: ArithExp' -> ArithExp
translate = undefined``````

(e) Write a non-standard `Eq` instance for `ArithExp'`, where `e1 == e2` iff they evaluate to the same number, e.g., `(Num' 2) == (Plus' (Num' 1) (Num' 1))` should return `True.

``````instance Eq ArithExp' where
e1 == e2 = undefined``````

Write a non-standard `Ord` instance for `ArithExp'` that goes with the `Eq` instance, i.e., `e1 < e2` iff `e1` evaluates to a lower number than `e2`, etc.

``````instance Ord ArithExp' where
compare e1 e2 = undefined``````

The `compare` function that you must implement for the `Ord` typeclass (interface) should return either `GT`, `LT`, or `EQ`, depending on the first parameter is greater than, less, than, or equal to the second.

Problem 2:  Functors

In Haskell, a functor is a container (like a list or a tree) with elements to which you can apply a function.  More technically, functor is a typeclass (interface) requiring a single function, `fmap`:

```class Functor f where
fmap :: (a -> b) -> f a -> f b```

Here, `(a -> b)` is the function you want to map, `f a` is a container with objects of type `a`, and the result is a container of type `b`.  In this problem we will create a couple of datatypes implementing this function.

(a) In the previous assignment we wrote a function `isBst` to determine whether a binary tree is a BST.  Now let’s  encode the BST directly:

``data BST a = Empty | Node (BST a) a (BST a)``

Define a `Functor` instance for `BST`.  To test your functor using my code, you’ll first need to define a `Show` instance for BST.  Here’s a bit of code to get you started:

``instance Show a => Show (BST a) where   ...instance Functor BST where   ... ``

(b)  The n-ary tree, trie, or rose tree data structure is a tree with an arbitrary number of children at each node. We can define it simply in Haskell:

``data RoseTree a = Leaf a | Branch [RoseTree a] deriving (Eq, Show)``

(Note that this definition subtly disagrees with the Wikipedia definition of rose trees by (a) having values at the leaves and (b) not having values at the nodes.)

Define a `Functor` instance for `RoseTree`.

``````instance Functor RoseTree where
fmap = undefined``````