# 99 questions/70B to 73

### From HaskellWiki

RossPaterson (Talk | contribs) |
(→Problem 70) |
||

(9 intermediate revisions by 4 users not shown) | |||

Line 1: | Line 1: | ||

__NOTOC__ | __NOTOC__ | ||

− | + | This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems]. | |

− | + | ||

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

Line 8: | Line 7: | ||

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

− | + | https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p70.gif | |

+ | |||

+ | == Problem 70B == | ||

+ | |||

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

+ | |||

+ | In Prolog or Lisp, one writes a predicate to check this. | ||

+ | |||

+ | Example in Prolog: | ||

+ | |||

+ | <pre> | ||

+ | ?- istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])). | ||

+ | Yes | ||

+ | </pre> | ||

+ | |||

+ | In Haskell, we define multiway trees as a datatype, as in the module [http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Tree.html Data.Tree]: | ||

+ | |||

<haskell> | <haskell> | ||

data Tree a = Node a [Tree a] | data Tree a = Node a [Tree a] | ||

deriving (Eq, Show) | deriving (Eq, Show) | ||

</haskell> | </haskell> | ||

+ | |||

Some example trees: | Some example trees: | ||

+ | |||

<haskell> | <haskell> | ||

tree1 = Node 'a' [] | tree1 = Node 'a' [] | ||

Line 30: | Line 47: | ||

</haskell> | </haskell> | ||

− | + | The last is the tree illustrated above. | |

− | + | As in problem 54A, all members of this type are multiway trees; there is no use for a predicate to test them. | |

− | + | ||

− | + | ||

== Problem 70C == | == Problem 70C == | ||

− | Count the nodes of a multiway tree. | + | (*) Count the nodes of a multiway tree. |

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

Tree> nnodes tree2 | Tree> nnodes tree2 | ||

2 | 2 | ||

− | </ | + | </haskell> |

− | + | [[99 questions/Solutions/70C | Solutions]] | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

== Problem 70 == | == Problem 70 == | ||

− | Tree construction from a node string. | + | (**) 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. | 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, <tt>tree5</tt> | + | By this rule, the tree below (<tt>tree5</tt>) is represented as: <tt>afg^^c^bd^e^^^</tt> |

+ | |||

+ | https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p70.gif | ||

Define the syntax of the string and write a predicate tree(String,Tree) to construct the Tree when the String is given. | 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. | Make your predicate work in both directions. | ||

− | + | Example in Haskell: | |

− | + | ||

− | |||

<haskell> | <haskell> | ||

− | + | Tree> stringToTree "afg^^c^bd^e^^^" | |

+ | Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]] | ||

− | + | Tree> treeToString (Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]]) | |

− | + | "afg^^c^bd^e^^^" | |

− | + | ||

− | + | ||

− | + | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

</haskell> | </haskell> | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | + | [[99 questions/Solutions/70 | Solutions]] | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | == 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: | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

<haskell> | <haskell> | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

Tree> ipl tree5 | Tree> ipl tree5 | ||

9 | 9 | ||

Tree> ipl tree4 | Tree> ipl tree4 | ||

2 | 2 | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

</haskell> | </haskell> | ||

+ | |||

+ | [[99 questions/Solutions/71 | Solutions]] | ||

+ | |||

== Problem 72 == | == Problem 72 == | ||

− | Construct the bottom-up order sequence of the tree nodes. | + | (*) 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. | Write a predicate bottom_up(Tree,Seq) which constructs the bottom-up sequence of the nodes of the multiway tree Tree. | ||

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

Tree> bottom_up tree5 | Tree> bottom_up tree5 | ||

"gfcdeba" | "gfcdeba" | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

</haskell> | </haskell> | ||

+ | |||

+ | [[99 questions/Solutions/72 | Solutions]] | ||

+ | |||

== Problem 73 == | == Problem 73 == | ||

− | Lisp-like tree representation. | + | (**) 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. | 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. | ||

+ | |||

+ | https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p73.png | ||

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

Line 215: | Line 139: | ||

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

Tree> display lisp tree1 | Tree> display lisp tree1 | ||

"a" | "a" | ||

Line 226: | Line 151: | ||

Tree> display lisp tree5 | Tree> display lisp tree5 | ||

"(a (f g) c (b d e))" | "(a (f g) c (b d e))" | ||

− | </ | + | </haskell> |

As a second, even more interesting exercise try to rewrite tree_ltl/2 in a way that the inverse conversion is also possible. | As a second, even more interesting exercise try to rewrite tree_ltl/2 in a way that the inverse conversion is also possible. | ||

− | + | [[99 questions/Solutions/73 | Solutions]] | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

[[Category:Tutorials]] | [[Category:Tutorials]] |

## Latest revision as of 00:43, 1 February 2012

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

## [edit] 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.

## [edit] 2 Problem 70B

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

In Prolog or Lisp, one writes a predicate to check this.

Example in Prolog:

?- istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])). Yes

In Haskell, we define multiway trees as a datatype, 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.

As in problem 54A, all members of this type are multiway trees; there is no use for a predicate to test them.

## [edit] 3 Problem 70C

(*) Count the nodes of a multiway tree.

Example in Haskell:

Tree> nnodes tree2 2

## [edit] 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.

Example in Haskell:

Tree> stringToTree "afg^^c^bd^e^^^" Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]] Tree> treeToString (Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]]) "afg^^c^bd^e^^^"

## [edit] 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

## [edit] 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"

## [edit] 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.