add expose to monads.ml
[lambda.git] / hints / assignment_10_hint_1.mdwn
1 We'll give you a hint, but it will require some extra thought.
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. See our [[state monad tutorial]] for explanation of `get` and `put`.
7
8 Also, you'll notice that this solution targets trees with labels on their inner nodes, instead of on their leaves. It shouldn't be too hard to get a similar strategy to work for leaf-labeled trees.
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
50         
51         ~~> Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil
52