Personal tools

99 questions/54A to 60

From HaskellWiki

< 99 questions(Difference between revisions)
Jump to: navigation, search
m (Formatting)
(Leaf -> Empty)
Line 20: Line 20:
 
The typical solution in Haskell is to introduce an algebraic data type:
 
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>
   
Line 37: Line 37:
   
 
<haskell>
 
<haskell>
*M> istree Leaf
+
*M> istree Empty
 
True
 
True
   
*M> istree (Branch 1 Leaf Leaf)
+
*M> istree (Branch 1 Empty Empty)
 
True
 
True
   
*M> istree (Branch 1 Leaf (Branch 2 Leaf Leaf))
+
*M> istree (Branch 1 Empty (Branch 2 Empty Empty))
 
True
 
True
 
</haskell>
 
</haskell>
Line 66: Line 66:
 
<pre>
 
<pre>
 
*Main> cbalTree 4
 
*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)]
+
[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)]
 
</pre>
 
</pre>
   
 
Solution:
 
Solution:
 
<haskell>
 
<haskell>
cbalTree 0 = [Leaf]
+
cbalTree 0 = [Empty]
 
cbalTree n = [Branch 'x' l r | i <- [q .. q + r], l <- cbalTree i, r <- cbalTree (n - i - 1)]
 
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
 
where (q, r) = quotRem (n-1) 2
Line 86: Line 86:
 
Example in Haskell:
 
Example in Haskell:
 
<pre>
 
<pre>
*Main> symmetric (Branch 'x' (Branch 'x' Leaf Leaf) Leaf)
+
*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>
 
</pre>
Line 94: Line 94:
 
Solution:
 
Solution:
 
<haskell>
 
<haskell>
mirror Leaf Leaf = True
+
mirror Empty Empty = True
 
mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x
 
mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x
 
mirror _ _ = False
 
mirror _ _ = False
   
symmetric Leaf = True
+
symmetric Empty = True
 
symmetric (Branch _ l r) = mirror l r
 
symmetric (Branch _ l r) = mirror l r
 
</haskell>
 
</haskell>
Line 127: Line 127:
 
<pre>
 
<pre>
 
*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>
 
</pre>
Line 137: Line 137:
 
<haskell>
 
<haskell>
 
add :: Ord a => a -> Tree a -> Tree a
 
add :: Ord a => a -> Tree a -> Tree a
add x Leaf = Branch x Leaf Leaf
+
add x Empty = Branch x Empty Empty
 
add x t@(Branch y l r) = case compare x y of
 
add x t@(Branch y l r) = case compare x y of
 
LT -> Branch y (add x l) r
 
LT -> Branch y (add x l) r
Line 143: Line 143:
 
EQ -> t
 
EQ -> t
   
construct xs = foldl (flip add) Leaf xs
+
construct xs = foldl (flip add) Empty xs
 
</haskell>
 
</haskell>
   
Line 163: Line 163:
 
<pre>
 
<pre>
 
*Main> symCbalTrees 5
 
*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))]
+
[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>
 
</pre>
   

Revision as of 02:21, 14 December 2006


These are Haskell translations of Ninety Nine Lisp 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 Problem 54A

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

Example:

* (istree (a (b nil nil) nil))
T
* (istree (a (b nil nil)))
NIL

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

data Tree a = Empty | Branch a (Tree a) (Tree a)
        deriving (Show, Eq)
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 -- the istree predicate is trivially true, for

anything of type
Tree a
.
istree :: Tree a -> Bool
istree _ = True

Running this:

*M> istree Empty
True
 
*M> istree (Branch 1 Empty Empty)
True
 
*M> istree (Branch 1 Empty (Branch 2 Empty Empty))
True

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

*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 (n-1) 2

Here we use the list monad to enumerate all the trees, in a style that is more natural than standard backtracking.

3 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

4 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

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.

5 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))]

Solution:

symCbalTrees = filter symmetric . cbalTree

6 Problem 59

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

7 Problem 60

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>