Personal tools

99 questions/54A to 60

From HaskellWiki

< 99 questions(Difference between revisions)
Jump to: navigation, search
m (new URL)
(moved solutions to subpages of 99 questions/Solutions and cleaned up code formatting)
Line 18: Line 18:
   
 
Example in Lisp:
 
Example in Lisp:
  +
 
<pre>
 
<pre>
 
* (istree (a (b nil nil) nil))
 
* (istree (a (b nil nil) nil))
Line 25: Line 26:
 
</pre>
 
</pre>
   
In Haskell, we characterize binary trees with a datatype definition:
+
[[99 questions/Solutions/54A | Solutions]]
<haskell>
 
data Tree a = Empty | Branch a (Tree a) (Tree a)
 
deriving (Show, Eq)
 
</haskell>
 
The above tree is represented as:
 
<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>
 
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)
 
</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 ==
Line 46: Line 38:
   
 
Example:
 
Example:
  +
 
<pre>
 
<pre>
 
* cbal-tree(4,T).
 
* cbal-tree(4,T).
Line 54: Line 47:
   
 
Example in Haskell, whitespace and "comment diagrams" added for clarity and exposition:
 
Example in Haskell, whitespace and "comment diagrams" added for clarity and exposition:
<pre>
+
  +
<haskell>
 
*Main> cbalTree 4
 
*Main> cbalTree 4
 
[
 
[
Line 97: Line 90:
 
(Branch 'x' Empty Empty)
 
(Branch 'x' Empty Empty)
 
]
 
]
</pre>
+
</haskell>
   
Solution:
+
[[99 questions/Solutions/55 | Solutions]]
<haskell>
 
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 (n-1) 2
 
</haskell>
 
   
Here we use the list monad to enumerate all the trees, in a style that is more natural than standard backtracking.
 
 
 
 
== Problem 56 ==
 
== Problem 56 ==
Line 110: Line 102:
   
 
Example in Haskell:
 
Example in Haskell:
<pre>
+
  +
<haskell>
 
*Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
 
*Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
 
False
 
False
 
*Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
 
*Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
 
True
 
True
</pre>
+
</haskell>
   
Solution:
+
[[99 questions/Solutions/56 | Solutions]]
<haskell>
 
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
 
</haskell>
 
 
 
 
== Problem 57 ==
 
== Problem 57 ==
Line 130: Line 119:
   
 
Example:
 
Example:
  +
 
<pre>
 
<pre>
 
* construct([3,2,5,7,1],T).
 
* construct([3,2,5,7,1],T).
Line 138: Line 128:
   
 
Example:
 
Example:
  +
 
<pre>
 
<pre>
 
* test-symmetric([5,3,18,1,4,12,21]).
 
* test-symmetric([5,3,18,1,4,12,21]).
Line 146: Line 137:
   
 
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 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty))
 
Branch 3 (Branch 2 (Branch 1 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty))
Line 153: Line 144:
 
*Main> symmetric . construct $ [3, 2, 5, 7, 1]
 
*Main> symmetric . construct $ [3, 2, 5, 7, 1]
 
True
 
True
</pre>
+
</haskell>
   
Solution:
+
[[99 questions/Solutions/57 | Solutions]]
<haskell>
 
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
 
</haskell>
 
   
Here, the definition of construct is trivial, because the pattern of accumulating from the left is captured by the standard function foldl.
 
 
 
 
== Problem 58 ==
 
== Problem 58 ==
Line 166: Line 156:
   
 
Example:
 
Example:
  +
 
<pre>
 
<pre>
 
* sym-cbal-trees(5,Ts).
 
* sym-cbal-trees(5,Ts).
Line 172: Line 163:
   
 
Example in Haskell:
 
Example in Haskell:
<pre>
 
*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))]
 
</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 ==
Line 189: Line 178:
   
 
Example:
 
Example:
  +
 
<pre>
 
<pre>
 
?- hbal_tree(3,T).
 
?- hbal_tree(3,T).
Line 197: Line 187:
   
 
Example in Haskell:
 
Example in Haskell:
<pre>
+
  +
<haskell>
 
*Main> take 4 $ hbalTree 'x' 3
 
*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' Empty (Branch 'x' Empty Empty)),
Line 203: Line 193:
 
Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' 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)]
 
Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' Empty Empty)]
</pre>
+
</haskell>
  +
  +
[[99 questions/Solutions/59 | Solutions]]
   
Solution:
 
<haskell>
 
hbalTree x = map fst . hbalTree'
 
where hbalTree' 0 = [(Empty, 0)]
 
hbalTree' 1 = [(Branch x Empty Empty, 1)]
 
hbalTree' n =
 
let t = hbalTree' (n-2) ++ hbalTree' (n-1)
 
in [(Branch x lb rb, h) | (lb,lh) <- t, (rb,rh) <- t
 
, let h = 1 + max lh rh, h == n]
 
</haskell>
 
Alternative solution:
 
<haskell>
 
hbaltree :: a -> Int -> [Tree a]
 
hbaltree x 0 = [Empty]
 
hbaltree x 1 = [Branch x Empty Empty]
 
hbaltree x h = [Branch x l r |
 
(hl, hr) <- [(h-2, h-1), (h-1, h-1), (h-1, h-2)],
 
l <- hbaltree x hl, r <- hbaltree x hr]
 
</haskell>
 
If we want to avoid recomputing lists of trees (at the cost of extra space), we can use a similar structure to the common method for computation of all the Fibonacci numbers:
 
<haskell>
 
hbaltree :: a -> Int -> [Tree a]
 
hbaltree x h = trees !! h
 
where trees = [Empty] : [Branch x Empty Empty] :
 
zipWith combine (tail trees) trees
 
combine ts shortts = [Branch x l r |
 
(ls, rs) <- [(shortts, ts), (ts, ts), (ts, shortts)],
 
l <- ls, r <- rs]
 
</haskell>
 
   
 
== Problem 60 ==
 
== Problem 60 ==
   
 
(**) Construct height-balanced binary trees with a given number of nodes
 
(**) Construct height-balanced binary trees with a given number of nodes
Consider a height-balanced 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 height-balanced binary tree of height H.
 
   
On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have?
+
Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain?
Write a function <hask>maxHeight</hask> that computes this.
 
   
Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes.
+
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 height-balanced binary tree of height H.
   
Find out how many height-balanced trees exist for N = 15.
+
On the other hand, we might ask: what is the maximum height H a height-balanced 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 height-balanced binary trees with a given nuber of nodes. Find out how many height-balanced trees exist for N = 15.
   
 
Example in Prolog:
 
Example in Prolog:
  +
 
<pre>
 
<pre>
 
?- count_hbal_trees(15,C).
 
?- count_hbal_trees(15,C).
Line 258: Line 214:
   
 
Example in Haskell:
 
Example in Haskell:
<pre>
+
  +
<haskell>
 
*Main> length $ hbalTreeNodes 'x' 15
 
*Main> length $ hbalTreeNodes 'x' 15
 
1553
 
1553
Line 266: Line 222:
 
[Branch 'x' Empty (Branch 'x' Empty Empty),Branch 'x' (Branch 'x' Empty 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)]]
 
[Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)]]
</pre>
 
 
Solution:
 
<haskell>
 
hbalTreeNodes _ 0 = [Empty]
 
hbalTreeNodes x n = concatMap toFilteredTrees [minHeight .. maxHeight]
 
where toFilteredTrees = filter ((n ==) . countNodes) . hbalTree x
 
 
-- Similar to the Fibonacci sequence but adds 1 in each step.
 
minNodesSeq = 0:1:zipWith ((+).(1+)) minNodesSeq (tail minNodesSeq)
 
minNodes = (minNodesSeq !!)
 
 
minHeight = ceiling $ logBase 2 $ fromIntegral (n+1)
 
maxHeight = (fromJust $ findIndex (>n) minNodesSeq) - 1
 
 
countNodes Empty = 0
 
countNodes (Branch _ l r) = countNodes l + countNodes r + 1
 
 
 
</haskell>
 
</haskell>
Another solution generates only the trees we want:
 
<haskell>
 
-- maximum number of nodes in a weight-balanced tree of height h
 
maxNodes :: Int -> Int
 
maxNodes h = 2^h - 1
 
   
-- minimum height of a weight-balanced tree of n nodes
+
[[99 questions/Solutions/60 | Solutions]]
minHeight :: Int -> Int
 
minHeight n = ceiling $ logBase 2 $ fromIntegral (n+1)
 
   
-- minimum number of nodes in a weight-balanced tree of height h
 
minNodes :: Int -> Int
 
minNodes h = fibs !! (h+2) - 1
 
 
-- maximum height of a weight-balanced tree of n nodes
 
maxHeight :: Int -> Int
 
maxHeight n = length (takeWhile (<= n+1) fibs) - 3
 
 
-- Fibonacci numbers
 
fibs :: [Int]
 
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
 
hbalTreeNodes :: a -> Int -> [Tree a]
 
hbalTreeNodes x n = [t | h <- [minHeight n .. maxHeight n], t <- baltree h n]
 
where
 
-- baltree h n = weight-balanced trees of height h with n nodes
 
-- assuming minNodes h <= n <= maxNodes h
 
baltree 0 n = [Empty]
 
baltree 1 n = [Branch x Empty Empty]
 
baltree h n = [Branch x l r |
 
(hl,hr) <- [(h-2,h-1), (h-1,h-1), (h-1,h-2)],
 
let min_nl = max (minNodes hl) (n - 1 - maxNodes hr),
 
let max_nl = min (maxNodes hl) (n - 1 - minNodes hr),
 
nl <- [min_nl .. max_nl],
 
let nr = n - 1 - nl,
 
l <- baltree hl nl,
 
r <- baltree hr nr]
 
</haskell>
 
   
 
[[Category:Tutorials]]
 
[[Category:Tutorials]]

Revision as of 21:48, 13 July 2010


This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine 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.

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.

p67.gif

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

Solutions


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 cbal-tree 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:

* cbal-tree(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)
]

Solutions


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

Solutions


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:

* test-symmetric([5,3,18,1,4,12,21]).
Yes
* test-symmetric([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

Solutions


6 Problem 58

(**) Generate-and-test paradigm

Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.

Example:

* sym-cbal-trees(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))]

Solutions


7 Problem 59

(**) Construct height-balanced binary trees

In a height-balanced 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)]

Solutions


8 Problem 60

(**) Construct height-balanced binary trees with a given number of nodes

Consider a height-balanced 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
minNodes
that returns the minimum number of nodes in a height-balanced binary tree of height H. On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have? Write a function
maxHeight
that computes this.

Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes. Find out how many height-balanced 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,1,2,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)]]

Solutions