Difference between revisions of "99 questions/70B to 73"
RossPaterson (talk  contribs) 
m (unify ghci prompts) 

(10 intermediate revisions by 4 users not shown)  
Line 1:  Line 1:  
__NOTOC__ 
__NOTOC__ 

−  These are Haskell translations of [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L99_NinetyNine_Lisp_Problems.html Ninety Nine Lisp Problems], 

+  This is part of [[H99:_NinetyNine_Haskell_ProblemsNinetyNine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p99/ NinetyNine Prolog Problems]. 

−  which are themselves translations of [http://www.htabi.bfh.ch/~hew/informatik3/prolog/p99/ NinetyNine 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. 

−  A Haskell implementation of multiway trees, as in the module [http://www.haskell.org/ghc/docs/latest/html/libraries/base/DataTree.html Data.Tree]: 

+  https://prof.ti.bfh.ch/hew1/informatik3/prolog/p99/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/DataTree.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> 

−  == Problem 70B == 

+  The last is the tree illustrated above. 

−  Check whether a given term represents a multiway tree. 

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

−  
−  This is trivial in a strongly typed language like Haskell. 

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

−  Count the nodes of a multiway tree. 
+  (*) Count the nodes of a multiway tree. 
Example in Haskell: 
Example in Haskell: 

−  <pre> 

−  Tree> nnodes tree2 

−  2 

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  nnodes 
+  λ> nnodes tree2 
−  +  2 

</haskell> 
</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 depthfirst 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 depthfirst 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/p99/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. 

−  Solution: 

+  Example in Haskell: 

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

<haskell> 
<haskell> 

−  newtype P a = P { runP :: String > Maybe (a, String) } 

+  λ> stringToTree "afg^^c^bd^e^^^" 

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

−  instance Monad P where 

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

−  return x = P $ \ s > Just (x, s) 

+  "afg^^c^bd^e^^^" 

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

</haskell> 
</haskell> 

−  Next a <tt>Syntax</tt> type, combining printing and parsing functions: 

−  <haskell> 

−  data Syntax a = Syntax { 

−  display :: a > String, 

−  parse :: P a 

−  } 

−  </haskell> 

−  (We don't use a class, because we want multiple syntaxes for a given type.) 

−  Some combinators for building syntaxes: 

−  <haskell> 

−   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 

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

−  (<>) :: 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 

+  == Problem 71 == 

−  char = Syntax return charP 

−  literal :: Char > Syntax () 

+  (*) Determine the internal path length of a tree. 

−  literal c = Syntax (const [c]) (literalP c) 

−  space :: Syntax () 

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

−  space = Syntax (const " ") spaceP 

−  iso :: (a > b) > (b > a) > Syntax a > Syntax b 

+  Example in Haskell: 

−  iso a_to_b b_to_a a = Syntax { 

−  display = display a . b_to_a, 

−  parse = liftM a_to_b (parse a) 

−  } 

−  </haskell> 

−  The last one maps a syntax using an isomorphism between types. 

−  Some uses of this function: 

−  <haskell> 

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

−  </haskell> 

−  Now we can define the syntax of depthfirst presentations: 

<haskell> 
<haskell> 

−  df :: Syntax (Tree Char) 

+  λ> ipl tree5 

−  df = iso toTree fromTree (char <*> list df (literal '^')) 

+  9 

−  where toTree (x, ts) = Node x ts 

+  λ> ipl tree4 

−  fromTree (Node x ts) = (x, ts) 

+  2 

</haskell> 
</haskell> 

−  We are using the isomorphism between <tt>Tree a</tt> and <tt>(a, [Tree a])</tt>. 

−  Some examples: 

−  <pre> 

−  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' []]],"") 

−  </pre> 

−  == Problem 71 == 

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

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

+  == Problem 72 == 

−  <pre> 

−  Tree> ipl tree5 

−  9 

−  Tree> ipl tree4 

−  2 

−  </pre> 

−  Solution: 

+  (*) Construct the bottomup order sequence of the tree nodes. 

−  <haskell> 

−  ipl :: Tree a > Int 

−  ipl = ipl' 0 

−  where ipl' d (Node _ ts) = d + sum (map (ipl' (d+1)) ts) 

−  </haskell> 

−  
−  == Problem 72 == 

−  Construct the bottomup order sequence of the tree nodes. 

Write a predicate bottom_up(Tree,Seq) which constructs the bottomup sequence of the nodes of the multiway tree Tree. 
Write a predicate bottom_up(Tree,Seq) which constructs the bottomup sequence of the nodes of the multiway tree Tree. 

Example in Haskell: 
Example in Haskell: 

−  <pre> 

−  Tree> bottom_up tree5 

−  "gfcdeba" 

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  bottom_up 
+  λ> bottom_up tree5 
−  +  "gfcdeba" 

−  </haskell> 

−  A more efficient version using an accumulator: 

−  <haskell> 

−  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 

</haskell> 
</haskell> 

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

+  
== Problem 73 == 
== Problem 73 == 

−  Lisplike tree representation. 
+  (**) Lisplike 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/p99/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 208:  Line 136:  
Example in Haskell: 
Example in Haskell: 

−  <pre> 

+  
−  Tree> display lisp tree1 

+  <haskell> 

+  λ> display lisp tree1 

"a" 
"a" 

−  +  λ> display lisp tree2 

"(a b)" 
"(a b)" 

−  +  λ> display lisp tree3 

"(a (b c))" 
"(a (b c))" 

−  +  λ> display lisp tree4 

"(b d e)" 
"(b d e)" 

−  +  λ> 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. 

−  Solution: 

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

−  using the <tt>Syntax</tt> type used in P70 above: 

+  
−  <haskell> 

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

−  </haskell> 

−  Here we use the isomorphism between <tt>Tree a</tt> and <tt>Either (a, [Tree a]) a</tt>, where the list is nonempty. 

[[Category:Tutorials]] 
[[Category:Tutorials]] 
Latest revision as of 09:37, 9 February 2019
This is part of NinetyNine Haskell Problems, based on NinetyNine 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.
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.
Problem 70C
(*) Count the nodes of a multiway tree.
Example in Haskell:
λ> nnodes tree2
2
Problem 70
(**) Tree construction from a node string.
We suppose that the nodes of a multiway tree contain single characters. In the depthfirst 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:
λ> stringToTree "afg^^c^bd^e^^^"
Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]]
λ> treeToString (Node 'a' [Node 'f' [Node 'g' []],Node 'c' [],Node 'b' [Node 'd' [],Node 'e' []]])
"afg^^c^bd^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:
λ> ipl tree5
9
λ> ipl tree4
2
Problem 72
(*) Construct the bottomup order sequence of the tree nodes.
Write a predicate bottom_up(Tree,Seq) which constructs the bottomup sequence of the nodes of the multiway tree Tree.
Example in Haskell:
λ> bottom_up tree5
"gfcdeba"
Problem 73
(**) Lisplike 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:
λ> display lisp tree1
"a"
λ> display lisp tree2
"(a b)"
λ> display lisp tree3
"(a (b c))"
λ> display lisp tree4
"(b d e)"
λ> 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.