Difference between revisions of "99 questions/70B to 73"

From HaskellWiki
Jump to: navigation, search
Line 130: Line 130:
The last one maps a syntax using an isomorphism (actually an embedding) between types.
The last one maps a syntax using an isomorphism between types.
Some uses of this function:
Some uses of this function:

Revision as of 01:13, 13 December 2006

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


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 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
Tree> runP (parse df) "afg^^c^bd^e^^^"
Just (Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]],"")

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
Tree> ipl tree4


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


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

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