Difference between revisions of "99 questions/54A to 60"
RossPaterson (talk  contribs) m 
RossPaterson (talk  contribs) (move data definition into 54A) 

Line 7:  Line 7:  
== Binary trees == 
== Binary trees == 

−  The type of binary trees: 

+  A binary tree is either empty or it is composed of a root element and two successors, which are binary trees themselves. 

−  <haskell> 

+  
−  data Tree a = Empty  Branch a (Tree a) (Tree a) 

+  http://www.htabi.bfh.ch/~hew/informatik3/prolog/p99/p67.gif 

−  deriving (Show, Eq) 

−  </haskell> 

−  An example tree: 

−  <haskell> 

−  tree1 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty)) 

−  (Branch 2 Empty Empty) 

−  </haskell> 

== Problem 54A == 
== Problem 54A == 

Line 22:  Line 15:  
(*) Check whether a given term represents a binary tree 
(*) Check whether a given term represents a binary tree 

−  Example: 

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

+  
+  Example in Lisp: 

<pre> 
<pre> 

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

Line 30:  Line 25:  
</pre> 
</pre> 

−  The type system ensures that all terms of type <haskell>Tree a</haskell> 

+  In Haskell, we characterize binary trees with a datatype definition: 

−  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  the istree predicate is trivially true, for 

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

−  
<haskell> 
<haskell> 

−  istree :: Tree a > Bool 

+  data Tree a = Empty  Branch a (Tree a) (Tree a) 

−  istree _ = True 

+  deriving (Show, Eq) 

</haskell> 
</haskell> 

−  
+  The above tree is represented as: 

−  Running this: 

+  <haskell> 

−  
+  tree1 = Branch 'a (Branch 'b' (Branch 'd' Empty Empty) 

+  (Branch 'e' Empty Empty)) 

+  (Branch 'c' Empty 

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

+  Empty))) 

+  </haskell> 

+  Other examples of binary trees: 

<haskell> 
<haskell> 

−  *M> istree Empty 

+  tree2 = Branch 'a' Empty Empty  a binary tree consisting of a root node only 

−  True 

−  *M> istree (Branch 1 Empty Empty) 

+  tree3 = nil  an empty binary tree 

−  True 

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

−  +  (Branch 2 Empty Empty) 

</haskell> 
</haskell> 

+  The 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 == 
Revision as of 00:06, 19 December 2006
This is part of NinetyNine Haskell Problems, based on 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
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
In Haskell, we characterize binary trees with a datatype definition:
data Tree a = Empty  Branch a (Tree a) (Tree a)
deriving (Show, Eq)
The above tree is 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)))
Other examples of binary trees:
tree2 = Branch 'a' Empty Empty  a binary tree consisting of a root node only
tree3 = nil  an empty binary tree
tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty))
(Branch 2 Empty Empty)
The type system ensures that all terms of type Tree a
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 True
.
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:
*Main> cbalTree 4 [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 (Branch 'x' Empty Empty)) (Branch 'x' Empty Empty),Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty Empty)]
Solution:
cbalTree 0 = [Empty]
cbalTree n = [Branch 'x' l r  i < [q .. q + r], l < cbalTree i, r < cbalTree (n  i  1)]
where (q, r) = quotRem (n1) 2
Here we use the list monad to enumerate all the trees, in a style that is more natural than standard backtracking.
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
Solution:
mirror Empty Empty = True
mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x
mirror _ _ = False
symmetric Empty = True
symmetric (Branch _ l r) = mirror l r
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,1]). 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
Solution:
add :: Ord a => a > Tree a > Tree a
add x Empty = Branch x Empty Empty
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) Empty xs
Here, the definition of construct is trivial, because the pattern of accumulating from the left is captured by the standard function foldl.
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))]
Solution:
symCbalTrees = filter symmetric . cbalTree
Problem 59
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 60
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>