Personal tools

99 questions/61 to 69

From HaskellWiki

< 99 questions(Difference between revisions)
Jump to: navigation, search
(descriptions for P64-66)
(solution to P65)
Line 131: Line 131:
 
Write a function to annotate each node of the tree with a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.
 
Write a function to annotate each node of the tree with a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.
   
Here is the example tree from the above illustration, which will also be used in the following two problems:
+
Here is the example tree from the above illustration:
 
<haskell>
 
<haskell>
 
tree2 = Branch 'n'
 
tree2 = Branch 'n'
Line 184: Line 184:
 
Use the same conventions as in problem P64 and test your function in an appropriate way.
 
Use the same conventions as in problem P64 and test your function in an appropriate way.
   
Example in Haskell:
+
Here is the example tree from the above illustration:
<pre>
+
<haskell>
<example in Haskell>
+
tree3 = Branch 'n'
</pre>
+
(Branch 'k'
  +
(Branch 'c'
  +
(Branch 'a' Empty Empty)
  +
(Branch 'e'
  +
(Branch 'd' Empty Empty)
  +
(Branch 'g' Empty Empty)
  +
)
  +
)
  +
(Branch 'm' Empty Empty)
  +
)
  +
(Branch 'u'
  +
(Branch 'p'
  +
Empty
  +
(Branch 'q' Empty Empty)
  +
)
  +
Empty
  +
)
  +
</haskell>
   
 
Solution:
 
Solution:
 
<haskell>
 
<haskell>
<solution in haskell>
+
layout :: Tree a -> Tree (a, Pos)
  +
layout t = layoutAux x1 1 sep1 t
  +
where d = depth t
  +
ld = leftdepth t
  +
x1 = 2^(d-1) - 2^(d-ld) + 1
  +
sep1 = 2^(d-2)
  +
layoutAux x y sep Empty = Empty
  +
layoutAux x y sep (Branch a l r) =
  +
Branch (a, (x,y))
  +
(layoutAux (x-sep) (y+1) (sep `div` 2) l)
  +
(layoutAux (x+sep) (y+1) (sep `div` 2) r)
  +
  +
depth :: Tree a -> Int
  +
depth Empty = 0
  +
depth (Branch a l r) = max (depth l) (depth r) + 1
  +
  +
leftdepth :: Tree a -> Int
  +
leftdepth Empty = 0
  +
leftdepth (Branch a l r) = leftdepth l + 1
 
</haskell>
 
</haskell>
  +
The auxiliary function is passed the x- and y-coordinates for the root of the subtree, the horizontal separation between the root and its child nodes, and the subtree itself.
  +
It returns the subtree annotated with positions.
   
<description of implementation>
 
 
 
== Problem 66 ==
 
== Problem 66 ==
   

Revision as of 01:13, 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 Binary trees

The type of binary trees:

data Tree a = Empty | Branch a (Tree a) (Tree a)
        deriving (Show, Eq)

An example tree:

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

2 Problem 61

Count the leaves of a binary tree

A leaf is a node with no successors. Write a predicate count_leaves/2 to count them.

Example:
% count_leaves(T,N) :- the binary tree T has N leaves

Example in Haskell:
> count_leaves tree1
2

Solution:

count_leaves  Empty                 = 0
count_leaves (Branch a Empty Empty) = 1
count_leaves (Branch a left  right) = count_leaves left + count_leaves right

3 Problem 61A

Collect the leaves of a binary tree in a list

A leaf is a node with no successors. Write a predicate leaves/2 to collect them in a list.

Example:
% leaves(T,S) :- S is the list of all leaves of the binary tree T

Example in Haskell:
> leaves tree1
[4, 2]

Solution:

leaves :: Tree a -> [a]
leaves  Empty                 = []
leaves (Branch a Empty Empty) = [a]
leaves (Branch a left  right) = leaves left ++ leaves right

4 Problem 62

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

5 Problem 62B

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

6 Problem 63

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

7 Problem 64

Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below:

p64.gif

In this layout strategy, the position of a node v is obtained by the following two rules:

  • x(v) is equal to the position of the node v in the inorder sequence
  • y(v) is equal to the depth of the node v in the tree

Write a function to annotate each node of the tree with a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.

Here is the example tree from the above illustration:

tree2 = Branch 'n'
                (Branch 'k'
                        (Branch 'c'
                                (Branch 'a' Empty Empty)
                                (Branch 'h'
                                        (Branch 'g'
                                                (Branch 'e' Empty Empty)
                                                Empty
                                        )
                                        Empty
                                )
                        )
                        (Branch 'm' Empty Empty)
                )
                (Branch 'u'
                        (Branch 'p'
                                Empty
                                (Branch 's'
                                        (Branch 'q' Empty Empty)
                                        Empty
                                )
                        )
                        Empty
                )

Solution:

type Pos = (Int, Int)
 
layout :: Tree a -> Tree (a, Pos)
layout t = fst (layoutAux 1 1 t)
  where layoutAux x y Empty = (Empty, x)
        layoutAux x y (Branch a l r) = (Branch (a, (x',y)) l' r', x'')
          where (l', x')  = layoutAux x (y+1) l
                (r', x'') = layoutAux (x'+1) (y+1) r

The auxiliary function is passed the x-coordinate for the left-most node of the subtree, the y-coordinate for the root of the subtree, and the subtree itself. It returns the subtree annotated with positions, plus the count of Branch nodes in the subtree.

8 Problem 65

An alternative layout method is depicted in the illustration below:

p65.gif

Find out the rules and write the corresponding function. Hint: On a given level, the horizontal distance between neighboring nodes is constant.

Use the same conventions as in problem P64 and test your function in an appropriate way.

Here is the example tree from the above illustration:

tree3 = Branch 'n'
                (Branch 'k'
                        (Branch 'c'
                                (Branch 'a' Empty Empty)
                                (Branch 'e'
                                        (Branch 'd' Empty Empty)
                                        (Branch 'g' Empty Empty)
                                )
                        )
                        (Branch 'm' Empty Empty)
                )
                (Branch 'u'
                        (Branch 'p'
                                Empty
                                (Branch 'q' Empty Empty)
                        )
                        Empty
                )

Solution:

layout :: Tree a -> Tree (a, Pos)
layout t = layoutAux x1 1 sep1 t
  where d = depth t
        ld = leftdepth t
        x1 = 2^(d-1) - 2^(d-ld) + 1
        sep1 = 2^(d-2)
        layoutAux x y sep Empty = Empty
        layoutAux x y sep (Branch a l r) =
                Branch (a, (x,y))
                        (layoutAux (x-sep) (y+1) (sep `div` 2) l)
                        (layoutAux (x+sep) (y+1) (sep `div` 2) r)
 
depth :: Tree a -> Int
depth Empty = 0
depth (Branch a l r) = max (depth l) (depth r) + 1
 
leftdepth :: Tree a -> Int
leftdepth Empty = 0
leftdepth (Branch a l r) = leftdepth l + 1

The auxiliary function is passed the x- and y-coordinates for the root of the subtree, the horizontal separation between the root and its child nodes, and the subtree itself. It returns the subtree annotated with positions.

9 Problem 66

Yet another layout strategy is shown in the illustration below:

p66.gif

The method yields a very compact layout while maintaining a certain symmetry in every node. Find out the rules and write the corresponding Prolog predicate. Hint: Consider the horizontal distance between a node and its successor nodes. How tight can you pack together two subtrees to construct the combined binary tree?

Use the same conventions as in problem P64 and P65 and test your predicate in an appropriate way. Note: This is a difficult problem. Don't give up too early!

Which layout do you like most?

<Problem description>

Example in Haskell:

<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

10 Problem 67

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

11 Problem 68

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

12 Problem 69

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>