99 questions/54A to 60
From HaskellWiki
DonStewart (Talk  contribs) (expand on why it is trivially true) 
(→Problem 60) 

(24 intermediate revisions by 7 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]. 
−  If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields. 
+  == Binary trees == 
−  +  A binary tree is either empty or it is composed of a root element and two successors, which are binary trees themselves. 

−  == Problem 54A == 

−  (*) Check whether a given term represents a binary tree 
+  https://prof.ti.bfh.ch/hew1/informatik3/prolog/p99/p67.gif 
−  Example: 
+  In Haskell, we can characterize binary trees with a datatype definition: 
−  <pre> 

−  * (istree (a (b nil nil) nil)) 

−  T 

−  * (istree (a (b nil nil))) 

−  NIL 

−  </pre> 

−  The typical solution in Haskell is to introduce an algebraic data type: 

<haskell> 
<haskell> 

−  data Tree a = Leaf  Branch a (Tree a) (Tree a) deriving Show 
+  data Tree a = Empty  Branch a (Tree a) (Tree a) 
+  deriving (Show, Eq) 

</haskell> 
</haskell> 

−  The type system ensures that all terms of type <haskell>Tree a</haskell> 
+  This says that a <tt>Tree</tt> of type <tt>a</tt> consists of either an <tt>Empty</tt> node, or a <tt>Branch</tt> containing one value of type <tt>a</tt> with exactly two subtrees of type <tt>a</tt>. 
−  are binary trees: it is just not possible to construct an invalid tree 
+  
−  using with this type. Hence, it is redundant to introduce a predicate to 
+  Given this definition, the tree in the diagram above would be represented as: 
−  check this property  the istree predicate is trivially true, for 

−  anything of type <hask>Tree a</hask>. 

<haskell> 
<haskell> 

−  istree :: Tree a > Bool 
+  tree1 = Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) 
−  istree _ = True 
+  (Branch 'e' Empty Empty)) 
+  (Branch 'c' Empty 

+  (Branch 'f' (Branch 'g' Empty Empty) 

+  Empty)) 

</haskell> 
</haskell> 

−  Running this: 
+  Since a "leaf" node is a branch with two empty subtrees, it can be useful to define a shorthand function: 
<haskell> 
<haskell> 

−  *M> istree Leaf 
+  leaf x = Branch x Empty Empty 
−  True 
+  </haskell> 
−  *M> istree (Branch 1 Leaf Leaf) 
+  Then the tree diagram above could be expressed more simply as: 
−  True 

−  *M> istree (Branch 1 Leaf (Branch 2 Leaf Leaf)) 
+  <haskell> 
−  True 
+  tree1' = Branch 'a' (Branch 'b' (leaf 'd') 
+  (leaf 'e')) 

+  (Branch 'c' Empty 

+  (Branch 'f' (leaf 'g') 

+  Empty))) 

</haskell> 
</haskell> 

+  
+  Other examples of binary trees: 

+  
+  <haskell> 

+   A binary tree consisting of a root node only 

+  tree2 = Branch 'a' Empty Empty 

+  
+   An empty binary tree 

+  tree3 = Empty 

+  
+   A tree of integers 

+  tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty)) 

+  (Branch 2 Empty Empty) 

+  </haskell> 

+  
+  == Problem 54A == 

+  
+  (*) Check whether a given term represents a binary tree 

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

+  
+  Example in Lisp: 

+  
+  <pre> 

+  * (istree (a (b nil nil) nil)) 

+  T 

+  * (istree (a (b nil nil))) 

+  NIL 

+  </pre> 

+  
+  Nonsolution: 

+  
+  Haskell's type system ensures that all terms of type <hask>Tree a</hask> are binary trees: it is just not possible to construct an invalid tree with this type. Hence, it is redundant to introduce a predicate to check this property: it would always return <hask>True</hask>. 

+  
== Problem 55 == 
== Problem 55 == 

(**) Construct completely balanced binary trees 
(**) Construct completely balanced binary trees 

+  
In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one. 
In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one. 

Write a function cbaltree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree. 
Write a function cbaltree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree. 

+  
Example: 
Example: 

+  
<pre> 
<pre> 

* cbaltree(4,T). 
* cbaltree(4,T). 

Line 51:  Line 87:  
</pre> 
</pre> 

−  Example in Haskell: 
+  Example in Haskell, whitespace and "comment diagrams" added for clarity and exposition: 
−  <pre> 

−  *Main> cbalTree 4 

−  [Branch 'x' (Branch 'x' Leaf Leaf) (Branch 'x' Leaf (Branch 'x' Leaf Leaf)),Branch 'x' (Branch 'x' Leaf Leaf) (Branch 'x' (Branch 'x' Leaf Leaf) Leaf),Branch 'x' (Branch 'x' Leaf (Branch 'x' Leaf Leaf)) (Branch 'x' Leaf Leaf),Branch 'x' (Branch 'x' (Branch 'x' Leaf Leaf) Leaf) (Branch 'x' Leaf Leaf)] 

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  cbalTree 0 = [Leaf] 
+  *Main> cbalTree 4 
−  cbalTree n = [Branch 'x' l r  i < [q .. q + r], l < cbalTree i, r < cbalTree (n  i  1)] 
+  [ 
−  where (q, r) = quotRem (n1) 2 
+   permutation 1 
+   x 

+   / \ 

+   x x 

+   \ 

+   x 

+  Branch 'x' (Branch 'x' Empty Empty) 

+  (Branch 'x' Empty 

+  (Branch 'x' Empty Empty)), 

+  
+   permutation 2 

+   x 

+   / \ 

+   x x 

+   / 

+   x 

+  Branch 'x' (Branch 'x' Empty Empty) 

+  (Branch 'x' (Branch 'x' Empty Empty) 

+  Empty), 

+  
+   permutation 3 

+   x 

+   / \ 

+   x x 

+   \ 

+   x 

+  Branch 'x' (Branch 'x' Empty 

+  (Branch 'x' Empty Empty)) 

+  (Branch 'x' Empty Empty), 

+  
+   permutation 4 

+   x 

+   / \ 

+   x x 

+   / 

+   x 

+  Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) 

+  Empty) 

+  (Branch 'x' Empty Empty) 

+  ] 

</haskell> 
</haskell> 

−  Here we use the list monad to enumerate all the trees, in a style that is more natural than standard backtracking. 
+  [[99 questions/Solutions/55  Solutions]] 
+  
== Problem 56 == 
== Problem 56 == 

(**) Symmetric binary trees 
(**) Symmetric binary trees 

+  
Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes. 
Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes. 

Example in Haskell: 
Example in Haskell: 

−  <pre> 
+  
−  *Main> symmetric (Branch 'x' (Branch 'x' Leaf Leaf) Leaf) 
+  <haskell> 
+  *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty) 

False 
False 

−  *Main> symmetric (Branch 'x' (Branch 'x' Leaf Leaf) (Branch 'x' Leaf Leaf)) 
+  *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)) 
True 
True 

−  </pre> 
+  </haskell> 
−  Solution: 
+  [[99 questions/Solutions/56  Solutions]] 
−  <haskell> 

−  mirror Leaf Leaf = True 

−  mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x 

−  mirror _ _ = False 

−  symmetric Leaf = True 

−  symmetric (Branch _ l r) = mirror l r 

−  </haskell> 

== Problem 57 == 
== Problem 57 == 

(**) Binary search trees (dictionaries) 
(**) Binary search trees (dictionaries) 

+  
Use the predicate add/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers. 
Use the predicate add/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers. 

+  
Example: 
Example: 

+  
<pre> 
<pre> 

* construct([3,2,5,7,1],T). 
* construct([3,2,5,7,1],T). 

Line 92:  Line 128:  
Then use this predicate to test the solution of the problem P56. 
Then use this predicate to test the solution of the problem P56. 

+  
Example: 
Example: 

+  
<pre> 
<pre> 

* testsymmetric([5,3,18,1,4,12,21]). 
* testsymmetric([5,3,18,1,4,12,21]). 

Yes 
Yes 

−  * testsymmetric([3,2,5,7,1]). 
+  * testsymmetric([3,2,5,7,4]). 
No 
No 

</pre> 
</pre> 

Example in Haskell: 
Example in Haskell: 

−  <pre> 
+  
+  <haskell> 

*Main> construct [3, 2, 5, 7, 1] 
*Main> construct [3, 2, 5, 7, 1] 

−  Branch 3 (Branch 2 (Branch 1 Leaf Leaf) (Branch 5 Leaf Leaf)) (Branch 7 Leaf Leaf) 
+  Branch 3 (Branch 2 (Branch 1 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty)) 
*Main> symmetric . construct $ [5, 3, 18, 1, 4, 12, 21] 
*Main> symmetric . construct $ [5, 3, 18, 1, 4, 12, 21] 

True 
True 

−  *Main> symmetric . construct $ [3, 2, 5, 7, 1] 
+  *Main> symmetric . construct $ [3, 2, 5, 7, 1] 
True 
True 

−  </pre> 

−  
−  Solution: 

−  <haskell> 

−  add :: Ord a => a > Tree a > Tree a 

−  add x Leaf = Branch x Leaf Leaf 

−  add x t@(Branch y l r) = case compare x y of 

−  LT > Branch y (add x l) r 

−  GT > Branch y l (add x r) 

−  EQ > t 

−  
−  construct xs = foldl (flip add) Leaf xs 

</haskell> 
</haskell> 

−  Here, the definition of construct is trivial, because the pattern of accumulating from the left is captured by the standard function foldl. 
+  [[99 questions/Solutions/57  Solutions]] 
+  
== Problem 58 == 
== Problem 58 == 

(**) Generateandtest paradigm 
(**) Generateandtest paradigm 

+  
Apply the generateandtest paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes. 
Apply the generateandtest paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes. 

+  
Example: 
Example: 

+  
<pre> 
<pre> 

* symcbaltrees(5,Ts). 
* symcbaltrees(5,Ts). 

Line 135:  Line 164:  
Example in Haskell: 
Example in Haskell: 

−  <pre> 

−  *Main> symCbalTrees 5 

−  [Branch 'x' (Branch 'x' Leaf (Branch 'x' Leaf Leaf)) (Branch 'x' (Branch 'x' Leaf Leaf) Leaf),Branch 'x' (Branch 'x' (Branch 'x' Leaf Leaf) Leaf) (Branch 'x' Leaf (Branch 'x' Leaf Leaf))] 

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  symCbalTrees = filter symmetric . cbalTree 
+  *Main> symCbalTrees 5 
+  [Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' (Branch 'x' Empty Empty) Empty),Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty (Branch 'x' Empty Empty))] 

</haskell> 
</haskell> 

+  
+  [[99 questions/Solutions/58  Solutions]] 

+  
== Problem 59 == 
== Problem 59 == 

−  <Problem description> 
+  (**) Construct heightbalanced binary trees 
+  
+  In a heightbalanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one. 

−  <pre> 

Example: 
Example: 

−  <example in lisp> 

−  Example in Haskell: 
+  <pre> 
−  <example in Haskell> 
+  ? hbal_tree(3,T). 
+  T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil))) ; 

+  T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil)) ; 

+  etc......No 

</pre> 
</pre> 

−  Solution: 
+  Example in Haskell: 
+  
<haskell> 
<haskell> 

−  <solution in haskell> 
+  *Main> take 4 $ hbalTree 'x' 3 
+  [Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty (Branch 'x' Empty Empty)), 

+  Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) Empty), 

+  Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)), 

+  Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' Empty Empty)] 

</haskell> 
</haskell> 

−  <description of implementation> 
+  [[99 questions/Solutions/59  Solutions]] 
−  +  
+  
== Problem 60 == 
== Problem 60 == 

−  <Problem description> 
+  (**) Construct heightbalanced binary trees with a given number of nodes 
+  
+  Consider a heightbalanced binary tree of height H. What is the maximum number of nodes it can contain? 

+  
+  Clearly, MaxN = 2**H  1. However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a function <hask>minNodes</hask> that returns the minimum number of nodes in a heightbalanced binary tree of height H. 

+  
+  On the other hand, we might ask: what is the maximum height H a heightbalanced binary tree with N nodes can have? Write a function <hask>maxHeight</hask> that computes this. 

+  
+  Now, we can attack the main problem: construct all the heightbalanced binary trees with a given number of nodes. Find out how many heightbalanced trees exist for N = 15. 

+  
+  Example in Prolog: 

<pre> 
<pre> 

−  Example: 
+  ? count_hbal_trees(15,C). 
−  <example in lisp> 
+  C = 1553 
+  </pre> 

Example in Haskell: 
Example in Haskell: 

−  <example in Haskell> 

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  <solution in haskell> 
+  *Main> length $ hbalTreeNodes 'x' 15 
+  1553 

+  *Main> map (hbalTreeNodes 'x') [0..3] 

+  [[Empty], 

+  [Branch 'x' Empty Empty], 

+  [Branch 'x' Empty (Branch 'x' Empty Empty),Branch 'x' (Branch 'x' Empty Empty) Empty], 

+  [Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)]] 

</haskell> 
</haskell> 

−  <description of implementation> 
+  [[99 questions/Solutions/60  Solutions]] 
−  +  
[[Category:Tutorials]] 
[[Category:Tutorials]] 
Revision as of 14:09, 21 January 2012
This is part of NinetyNine Haskell Problems, based on NinetyNine Prolog Problems.
1 Binary trees
A binary tree is either empty or it is composed of a root element and two successors, which are binary trees themselves.
In Haskell, we can characterize binary trees with a datatype definition:
data Tree a = Empty  Branch a (Tree a) (Tree a) deriving (Show, Eq)
This says that a Tree of type a consists of either an Empty node, or a Branch containing one value of type a with exactly two subtrees of type a.
Given this definition, the tree in the diagram above would be represented as:
tree1 = Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' Empty Empty)) (Branch 'c' Empty (Branch 'f' (Branch 'g' Empty Empty) Empty))
Since a "leaf" node is a branch with two empty subtrees, it can be useful to define a shorthand function:
leaf x = Branch x Empty Empty
Then the tree diagram above could be expressed more simply as:
tree1' = Branch 'a' (Branch 'b' (leaf 'd') (leaf 'e')) (Branch 'c' Empty (Branch 'f' (leaf 'g') Empty)))
Other examples of binary trees:
 A binary tree consisting of a root node only tree2 = Branch 'a' Empty Empty  An empty binary tree tree3 = Empty  A tree of integers tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty)) (Branch 2 Empty Empty)
2 Problem 54A
(*) Check whether a given term represents a binary tree
In Prolog or Lisp, one writes a predicate to do this.
Example in Lisp:
* (istree (a (b nil nil) nil)) T * (istree (a (b nil nil))) NIL
Nonsolution:
Haskell's type system ensures that all terms of type
3 Problem 55
(**) Construct completely balanced binary trees
In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.
Write a function cbaltree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.
Example:
* cbaltree(4,T). T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ; T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ; etc......No
Example in Haskell, whitespace and "comment diagrams" added for clarity and exposition:
*Main> cbalTree 4 [  permutation 1  x  / \  x x  \  x Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty (Branch 'x' Empty Empty)),  permutation 2  x  / \  x x  /  x Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) Empty),  permutation 3  x  / \  x x  \  x Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' Empty Empty),  permutation 4  x  / \  x x  /  x Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty Empty) ]
4 Problem 56
(**) Symmetric binary trees
Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes.
Example in Haskell:
*Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty) False *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)) True
5 Problem 57
(**) Binary search trees (dictionaries)
Use the predicate add/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers.
Example:
* construct([3,2,5,7,1],T). T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))
Then use this predicate to test the solution of the problem P56.
Example:
* testsymmetric([5,3,18,1,4,12,21]). Yes * testsymmetric([3,2,5,7,4]). No
Example in Haskell:
*Main> construct [3, 2, 5, 7, 1] Branch 3 (Branch 2 (Branch 1 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty)) *Main> symmetric . construct $ [5, 3, 18, 1, 4, 12, 21] True *Main> symmetric . construct $ [3, 2, 5, 7, 1] True
6 Problem 58
(**) Generateandtest paradigm
Apply the generateandtest paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
Example:
* symcbaltrees(5,Ts). Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]
Example in Haskell:
*Main> symCbalTrees 5 [Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' (Branch 'x' Empty Empty) Empty),Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty (Branch 'x' Empty Empty))]
7 Problem 59
(**) Construct heightbalanced binary trees
In a heightbalanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.
Example:
? hbal_tree(3,T). T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil))) ; T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil)) ; etc......No
Example in Haskell:
*Main> take 4 $ hbalTree 'x' 3 [Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty (Branch 'x' Empty Empty)), Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) Empty), Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)), Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' Empty Empty)]
8 Problem 60
(**) Construct heightbalanced binary trees with a given number of nodes
Consider a heightbalanced binary tree of height H. What is the maximum number of nodes it can contain?
Clearly, MaxN = 2**H  1. However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a functionNow, we can attack the main problem: construct all the heightbalanced binary trees with a given number of nodes. Find out how many heightbalanced trees exist for N = 15.
Example in Prolog:
? count_hbal_trees(15,C). C = 1553
Example in Haskell:
*Main> length $ hbalTreeNodes 'x' 15 1553 *Main> map (hbalTreeNodes 'x') [0..3] [[Empty], [Branch 'x' Empty Empty], [Branch 'x' Empty (Branch 'x' Empty Empty),Branch 'x' (Branch 'x' Empty Empty) Empty], [Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)]]