99 questions/Solutions/73 - Revision history
http://www.haskell.org/haskellwiki/index.php?title=99_questions/Solutions/73&action=history
Revision history for this page on the wikienMediaWiki 1.19.5-1+deb7u1Thu, 21 Aug 2014 15:35:56 GMTWapcaplet at 15:44, 15 July 2010
http://www.haskell.org/haskellwiki/index.php?title=99_questions/Solutions/73&diff=36205&oldid=prev
http://www.haskell.org/haskellwiki/index.php?title=99_questions/Solutions/73&diff=36205&oldid=prev<p></p>
<p><b>New page</b></p><div>(**) Lisp-like tree representation.<br />
<br />
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.<br />
<br />
The following pictures show how multiway tree structures are represented in Lisp.<br />
<br />
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p73.png<br />
<br />
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.<br />
<br />
Solution using the <tt>Syntax</tt> type used in problem 70 above:<br />
<br />
<haskell><br />
lisp :: Syntax (Tree Char)<br />
lisp = iso toTree fromTree<br />
(literal '(' *> (char <*> list (space *> lisp) (literal ')')) <|> char)<br />
where toTree (Left (x, ts)) = Node x ts<br />
toTree (Right x) = Node x []<br />
fromTree (Node x []) = Right x<br />
fromTree (Node x ts) = Left (x, ts)<br />
</haskell><br />
<br />
Here we use the isomorphism between <tt>Tree a</tt> and <tt>Either (a, [Tree a]) a</tt>, where the list is non-empty.</div>Thu, 15 Jul 2010 15:44:21 GMTWapcaplethttp://www.haskell.org/haskellwiki/Talk:99_questions/Solutions/73