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