post initial ass10

Signed-off-by: Jim Pryor <profjim@jimpryor.net>

diff --git a/assignment10.mdwn b/assignment10.mdwn
index ab5830a..c6cc2d5 100644 (file)
--- a/assignment10.mdwn
+++ b/assignment10.mdwn
@@ -1,54 +1,13 @@
--- from the Glasgow Haskell Compiler sources (/Control/Monad/State/Strict.hs)
 
--- An example from /The Craft of Functional Programming/, Simon
--- Thompson (<http://www.cs.kent.ac.uk/people/staff/sjt/>),
--- Addison-Wesley 1999: \"Given an arbitrary tree, transform it to a
--- tree of integers in which the original elements are replaced by
--- natural numbers, starting from 0.  The same element has to be
--- replaced by the same number at every occurrence, and when we meet
--- an as-yet-unvisited element we have to find a \'new\' number to match
--- it with:\"
---
--- > data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
--- > type Table a = [a]
---
--- > numberTree :: Eq a => Tree a -> State (Table a) (Tree Int)
--- > numberTree Nil = return Nil
--- > numberTree (Node x t1 t2)
--- >        =  do num <- numberNode x
--- >              nt1 <- numberTree t1
--- >              nt2 <- numberTree t2
--- >              return (Node num nt1 nt2)
--- >     where
--- >     numberNode :: Eq a => a -> State (Table a) Int
--- >     numberNode x
--- >        = do table <- get
--- >             (newTable, newPos) <- return (nNode x table)
--- >             put newTable
--- >             return newPos
--- >     nNode::  (Eq a) => a -> Table a -> (Table a, Int)
--- >     nNode x table
--- >        = case (findIndexInList (== x) table) of
--- >          Nothing -> (table ++ [x], length table)
--- >          Just i  -> (table, i)
--- >     findIndexInList :: (a -> Bool) -> [a] -> Maybe Int
--- >     findIndexInList = findIndexInListHelp 0
--- >     findIndexInListHelp _ _ [] = Nothing
--- >     findIndexInListHelp count f (h:t)
--- >        = if (f h)
--- >          then Just count
--- >          else findIndexInListHelp (count+1) f t
---
--- numTree applies numberTree with an initial state:
---
--- > numTree :: (Eq a) => Tree a -> Tree Int
--- > numTree t = evalState (numberTree t) []
---
--- > testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil
--- > numTree testTree => Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil
---
--- sumTree is a little helper function that does not use the State monad:
---
--- > sumTree :: (Num a) => Tree a -> a
--- > sumTree Nil = 0
--- > sumTree (Node e t1 t2) = e + (sumTree t1) + (sumTree t2)
+This problem is taken from _The Craft of Functional Programming_ by Simon Thompson, Addison-Wesley 1999 <http://www.cs.kent.ac.uk/people/staff/sjt/>:
+
+>      Given an arbitrary tree, transform it to a
+>      tree of integers in which the original elements are replaced by
+>      natural numbers, starting from 0.  The same element has to be
+>      replaced by the same number at every occurrence, and when we meet
+>      an as-yet-unvisited element we have to find a "new" number to match
+>      it with.
+
+
+Here is [a hint](/hints/assignment_10_hint).
+

diff --git a/hints/assignment_10_hint.mdwn b/hints/assignment_10_hint.mdwn
new file mode 100644 (file)
index 0000000..3e0915a
--- /dev/null
+++ b/hints/assignment_10_hint.mdwn
@@ -0,0 +1,50 @@
+We'll give you hint, but it will involve some extra work.
+
+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).
+
+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 
+[[translating between OCaml Scheme and Haskell]] for guidance.
+
+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.
+
+
+       data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
+       type Table a = [a]
+
+       numberTree :: Eq a => Tree a -> State (Table a) (Tree Int)
+       numberTree Nil = return Nil
+       numberTree (Node x t1 t2)
+                  =  do num <- numberNode x
+                                nt1 <- numberTree t1
+                                nt2 <- numberTree t2
+                                return (Node num nt1 nt2)
+               where
+               numberNode :: Eq a => a -> State (Table a) Int
+               numberNode x
+                  = do table <- get
+                               (newTable, newPos) <- return (nNode x table)
+                               put newTable
+                               return newPos
+               nNode::  (Eq a) => a -> Table a -> (Table a, Int)
+               nNode x table
+                  = case (findIndexInList (== x) table) of
+                        Nothing -> (table ++ [x], length table)
+                        Just i  -> (table, i)
+               findIndexInList :: (a -> Bool) -> [a] -> Maybe Int
+               findIndexInList = findIndexInListHelp 0
+               findIndexInListHelp _ _ [] = Nothing
+               findIndexInListHelp count f (h:t)
+                  = if (f h)
+                        then Just count
+                        else findIndexInListHelp (count+1) f t
+
+&nbsp;
+
+       -- numTree applies numberTree with an initial state:
+
+       numTree :: (Eq a) => Tree a -> Tree Int
+       numTree t = evalState (numberTree t) []
+
+       testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil
+       numTree testTree => Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil
+