X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment10.mdwn;h=c6cc2d533e6c23715aac250cc189763d96aaebf0;hp=ab5830a4c0a23ce7825b34774fab72b906830023;hb=fff7086c5dec8448c3a5369f3df88b50ffd06e6b;hpb=61144e14eacb1ce6fdd602962f5d77c11deed156 diff --git a/assignment10.mdwn b/assignment10.mdwn index ab5830a4..c6cc2d53 100644 --- 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 (), --- 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 : + +> 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). +