# 99 questions/70B to 73

### From HaskellWiki

RossPaterson (Talk | contribs) (pictures) |
RossPaterson (Talk | contribs) m |
||

Line 1: | Line 1: | ||

__NOTOC__ | __NOTOC__ | ||

− | + | This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [http://www.hta-bi.bfh.ch/~hew/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems]. | |

== Multiway Trees == | == Multiway Trees == |

## Revision as of 01:00, 15 December 2006

This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems.

## 1 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' []] ]

The last is the tree illustrated above.

## 2 Problem 70B

(*) Check whether a given term represents a multiway tree.

This is trivial in a strongly typed language like Haskell, as in problem 54A.

## 3 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)

## 4 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, the tree below (`tree5`) 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 we 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)

We are using the isomorphism between `Tree a` and `(a, [Tree a])`.
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' []]],"")

## 5 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, `tree5` has an internal path length of 9.

Example in Haskell:

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)

## 6 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

## 7 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.

The following pictures show how multiway tree structures are represented in Lisp.

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 problem 70 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)

Here we use the isomorphism between `Tree a` and `Either (a, [Tree a]) a`, where the list is non-empty.