hints/assignment_10_hint.mdwn

   1 We'll give you hint, but it will involve some extra work.
   2
   3 The hint is a solution to this exercise taken from the source code that accompanies the Glasgow Haskell Compiler. (Underneath /Control/Monad/State/Strict.hs).
   4
   5 We're not going to massage it in any way. If you want to make use of it, you'll have to figure out for yourself what's going on. This should be within your reach at this point. See our page on
   6 [[translating between OCaml Scheme and Haskell]] for guidance.
   7
   8 Also, you'll notice that this solution targets trees with labels on their inner nodes, instead of on their leaves. You should be able to get this to work for leaf-labeled trees, too.
   9
  10
  11         data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
  12         type Table a = [a]
  13
  14         numberTree :: Eq a => Tree a -> State (Table a) (Tree Int)
  15         numberTree Nil = return Nil
  16         numberTree (Node x t1 t2)
  17                    =  do num <- numberNode x
  18                                  nt1 <- numberTree t1
  19                                  nt2 <- numberTree t2
  20                                  return (Node num nt1 nt2)
  21                 where
  22                 numberNode :: Eq a => a -> State (Table a) Int
  23                 numberNode x
  24                    = do table <- get
  25                                 (newTable, newPos) <- return (nNode x table)
  26                                 put newTable
  27                                 return newPos
  28                 nNode::  (Eq a) => a -> Table a -> (Table a, Int)
  29                 nNode x table
  30                    = case (findIndexInList (== x) table) of
  31                          Nothing -> (table ++ [x], length table)
  32                          Just i  -> (table, i)
  33                 findIndexInList :: (a -> Bool) -> [a] -> Maybe Int
  34                 findIndexInList = findIndexInListHelp 0
  35                 findIndexInListHelp _ _ [] = Nothing
  36                 findIndexInListHelp count f (h:t)
  37                    = if (f h)
  38                          then Just count
  39                          else findIndexInListHelp (count+1) f t
  40
  41 &nbsp;
  42
  43         -- numTree applies numberTree with an initial state:
  44
  45         numTree :: (Eq a) => Tree a -> Tree Int
  46         numTree t = evalState (numberTree t) []
  47
  48         testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil
  49         numTree testTree => Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil
  50