Solutions to homework 4

Solutions will be added on request. If you would like the solution for a particular problem to be added, email the instructor.

3. Tree enumeration

3.2. Code (without monads)

This problem requires that the state of a counter be managed somehow. One way to do this is to pass the counter down and up the tree explicitly:

enumerateTree :: Int -> BinaryTree -> [(Int, String)]
enumerateTree i (LeafNode s) = [(i, s)]
enumerateTree i (InternalNode t1 t2)
    = (enumerateTree (j + 1) t2) ++ ((j, a):x)
    where 
    ((j, a):x) = (enumerateTree i t1)

Here, the next available counter value is passed down the tree by giving it as the first argument to enumerateTree.

Enumerating a LeafNode is simple: The result is just a pair of the next counter value and the name of the node. But how do we enumerate an internal node? Enumerating the left subtree (t1) is easy: We just pass i (the next available counter value) as the first argument when we call enumerateTree on t1.

But what should we give as the first argument when we call enumerateTree on the right subtree (t2)? The answer depends on how many leaves were enumerated in the left subtree. We therefore need to look at the result of enumerating the left subtree. That is what the above code does: It first calls enumerateTree i t1. The number from the first element of the result is given the name j, and it then calls enumerateTree (j + 1) t2. Finally, the results are appended with ++.

3.2. Code (with monads)

The code above can be confusing. We can abstract the mechanics of passing state around with a state monad. (See Section 18.8 and 18.9 of Simon Thompson's book.)

enumerateTree :: BinaryTree -> [(Int, String)]
enumerateTree = extract . numberTree

data State b = State (Int -> (Int, b))

numberTree :: BinaryTree -> State [(Int, String)]
numberTree (LeafNode name) 
    = do id <- numberNode
         return [(id, name)]
numberTree (InternalNode c1 c2)
    = do nt1 <- numberTree c1
         nt2 <- numberTree c2
         return (nt2 ++ nt1)

numberNode :: State Int
numberNode = State nNode

nNode :: Int -> (Int, Int)
nNode next = (next + 1, next)

instance Monad (State) where
    return id = State (\next -> (next, id))
    (State st) >>= f
        = State (\next -> let
                          (newNext, y) = st next
                          (State trans) = f y
                                          in
                          trans newNext)

extract :: State b -> b
extract (State st) = snd (st 1)