99 questions/70B to 73
These are Haskell translations of Ninety Nine Lisp Problems,
which are themselves translations of Ninety-Nine Prolog Problems.
Multiway Trees
A multiway tree is composed of a root element and a (possibly empty) set of successors which are multiway trees themselves. A multiway tree is never empty. The set of successor trees is sometimes called a forest.
A Haskell implementation of multiway trees, as in the module Data.Tree:
data Tree a = Node a [Tree a]
deriving (Eq, Show)
Some example trees:
tree1 = Node 'a' []
tree2 = Node 'a' [Node 'b' []]
tree3 = Node 'a' [Node 'b' [Node 'c' []]]
tree4 = Node 'b' [Node 'd' [], Node 'e' []]
tree5 = Node 'a' [
Node 'f' [Node 'g' []],
Node 'c' [],
Node 'b' [Node 'd' [], Node 'e' []]
]
Problem 70B
Check whether a given term represents a multiway tree.
This is trivial in a strongly typed language like Haskell.
Problem 70C
Count the nodes of a multiway tree.
Example in Haskell:
Tree> nnodes tree2 2
Solution:
nnodes :: Tree a -> Int
nnodes (Node _ ts) = 1 + sum (map nnodes ts)
Problem 70
Tree construction from a node string.
We suppose that the nodes of a multiway tree contain single characters. In the depth-first order sequence of its nodes, a special character ^ has been inserted whenever, during the tree traversal, the move is a backtrack to the previous level.
By this rule, tree5 above is represented as: afg^^c^bd^e^^^
Define the syntax of the string and write a predicate tree(String,Tree) to construct the Tree when the String is given. Make your predicate work in both directions.
Solution: We could write separate printing and parsing functions, but the problem statement asks for a bidirectional function.
First we need a parser monad, with some primitives:
newtype P a = P { runP :: String -> Maybe (a, String) }
instance Monad P where
return x = P $ \ s -> Just (x, s)
P v >>= f = P $ \ s -> do
(x, s') <- v s
runP (f x) s'
instance MonadPlus P where
mzero = P $ \ _ -> Nothing
P u `mplus` P v = P $ \ s -> u s `mplus` v s
charP :: P Char
charP = P view_list
where view_list [] = Nothing
view_list (c:cs) = Just (c, cs)
literalP :: Char -> P ()
literalP c = do { c' <- charP; guard (c == c') }
spaceP :: P ()
spaceP = P (\ s -> Just ((), dropWhile isSpace s))
Next a Syntax type, combining printing and parsing functions:
data Syntax a = Syntax {
display :: a -> String,
parse :: P a
}
(We don't use a class, because we want multiple syntaxes for a given type.) Some combinators for building syntaxes:
-- concatenation
(<*>) :: Syntax a -> Syntax b -> Syntax (a,b)
a <*> b = Syntax {
display = \ (va,vb) -> display a va ++ display b vb,
parse = liftM2 (,) (parse a) (parse b)
}
-- alternatives
(<|>) :: Syntax a -> Syntax b -> Syntax (Either a b)
a <|> b = Syntax {
display = either (display a) (display b),
parse = liftM Left (parse a) `mplus` liftM Right (parse b)
}
char :: Syntax Char
char = Syntax return charP
literal :: Char -> Syntax ()
literal c = Syntax (const [c]) (literalP c)
space :: Syntax ()
space = Syntax (const " ") spaceP
iso :: (a -> b) -> (b -> a) -> Syntax a -> Syntax b
iso a_to_b b_to_a a = Syntax {
display = display a . b_to_a,
parse = liftM a_to_b (parse a)
}
The last one maps a syntax using an isomorphism between types. Some uses of this function:
-- concatenation, with no value in the first part
(*>) :: Syntax () -> Syntax a -> Syntax a
p *> q = iso snd ((,) ()) (p <*> q)
-- list of a's, followed by finish
list :: Syntax a -> Syntax () -> Syntax [a]
list a finish = iso toList fromList (finish <|> (a <*> list a finish))
where toList (Left _) = []
toList (Right (x, xs)) = x:xs
fromList [] = Left ()
fromList (x:xs) = Right (x, xs)
Now be can define the syntax of depth-first presentations:
df :: Syntax (Tree Char)
df = iso toTree fromTree (char <*> list df (literal '^'))
where toTree (x, ts) = Node x ts
fromTree (Node x ts) = (x, ts)
Some examples:
Tree> display df tree5 "afg^^c^bd^e^^^" Tree> runP (parse df) "afg^^c^bd^e^^^" Just (Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]],"") </haskell> == Problem 71 == Determine the internal path length of a tree. We define the internal path length of a multiway tree as the total sum of the path lengths from the root to all nodes of the tree. By this definition, <tt>tree5</tt> has an internal path length of 9. Example in Haskell: <pre> Tree> ipl tree5 9 Tree> ipl tree4 2
Solution:
ipl :: Tree a -> Int
ipl = ipl' 0
where ipl' d (Node _ ts) = d + sum (map (ipl' (d+1)) ts)
Problem 72
Construct the bottom-up order sequence of the tree nodes. Write a predicate bottom_up(Tree,Seq) which constructs the bottom-up sequence of the nodes of the multiway tree Tree.
Example in Haskell:
Tree> bottom_up tree5 "gfcdeba"
Solution:
bottom_up :: Tree a -> [a]
bottom_up (Node x ts) = concatMap bottom_up ts ++ [x]
A more efficient version using an accumulator:
bottom_up :: Tree a -> [a]
bottom_up t = bottom_up_aux t []
where bottom_up_aux :: Tree a -> [a] -> [a]
bottom_up_aux (Node x ts) xs = foldr bottom_up_aux (x:xs) ts
Problem 73
Lisp-like tree representation. There is a particular notation for multiway trees in Lisp. Lisp is a prominent functional programming language, which is used primarily for artificial intelligence problems. As such it is one of the main competitors of Prolog. In Lisp almost everything is a list, just as in Prolog everything is a term.
Note that in the "lispy" notation a node with successors (children) in the tree is always the first element in a list, followed by its children. The "lispy" representation of a multiway tree is a sequence of atoms and parentheses '(' and ')', which we shall collectively call "tokens". We can represent this sequence of tokens as a Prolog list; e.g. the lispy expression (a (b c)) could be represented as the Prolog list ['(', a, '(', b, c, ')', ')']. Write a predicate tree_ltl(T,LTL) which constructs the "lispy token list" LTL if the tree is given as term T in the usual Prolog notation.
(The Prolog example given is incorrect.)
Example in Haskell:
Tree> display lisp tree1 "a" Tree> display lisp tree2 "(a b)" Tree> display lisp tree3 "(a (b c))" Tree> display lisp tree4 "(b d e)" Tree> display lisp tree5 "(a (f g) c (b d e))"
As a second, even more interesting exercise try to rewrite tree_ltl/2 in a way that the inverse conversion is also possible.
Solution: using the Syntax type used in P70 above:
lisp :: Syntax (Tree Char)
lisp = iso toTree fromTree
(literal '(' *> (char <*> list (space *> lisp) (literal ')')) <|> char)
where toTree (Left (x, ts)) = Node x ts
toTree (Right x) = Node x []
fromTree (Node x []) = Right x
fromTree (Node x ts) = Left (x, ts)