**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

**typeclass (interface) should return either**

`Ord`

**,**

`GT`

**, or**

`LT`

**, depending on the first parameter is greater than, less, than, or equal to the second.**

`EQ`

**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,

**is a container with objects of type**

`f a`

**, and the result is a container of type**

`a`

**. In this problem we will create a couple of datatypes implementing this function.**

`b`

*(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
```