# 99 questions/61 to 69

### From HaskellWiki

RossPaterson (Talk | contribs) m |
RossPaterson (Talk | contribs) m (align with previous page) |
||

Line 7: | Line 7: | ||

== Binary trees == |
== Binary trees == |
||

− | The type of binary trees: |
+ | As defined in problem 54A. |

− | <haskell> |
+ | |

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

− | deriving (Show, Eq) |
||

− | </haskell> |
||

An example tree: |
An example tree: |
||

<haskell> |
<haskell> |
||

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

(Branch 2 Empty Empty) |
(Branch 2 Empty Empty) |
||

</haskell> |
</haskell> |
||

Line 26: | Line 26: | ||

Example in Haskell: |
Example in Haskell: |
||

− | > count_leaves tree1 |
+ | > count_leaves tree4 |

2 |
2 |
||

</pre> |
</pre> |
||

Line 48: | Line 48: | ||

Example in Haskell: |
Example in Haskell: |
||

− | > leaves tree1 |
+ | > leaves tree4 |

[4, 2] |
[4, 2] |
||

</pre> |
</pre> |
||

Line 70: | Line 70: | ||

Example in Haskell: |
Example in Haskell: |
||

− | Prelude>internals tree1 |
+ | Prelude>internals tree4 |

Prelude>[1,2] |
Prelude>[1,2] |
||

</pre> |
</pre> |
||

Line 92: | Line 92: | ||

Example in Haskell: |
Example in Haskell: |
||

− | Prelude>atlevel tree1 2 |
+ | Prelude>atlevel tree4 2 |

Prelude>[2,2] |
Prelude>[2,2] |
||

</pre> |
</pre> |

## Revision as of 00:10, 19 December 2006

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

As defined in problem 54A.

An example tree:

tree4 = 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 tree4 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 tree4 [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

Collect the internal nodes of a binary tree in a list An internal node of a binary tree has either one or two non-empty successors. Write a predicate internals/2 to collect them in a list.

Example: % internals(T,S) :- S is the list of internal nodes of the binary tree T. Example in Haskell: Prelude>internals tree4 Prelude>[1,2]

Solution:

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

## 5 Problem 62B

Collect the nodes at a given level in a list A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list.

Example: % atlevel(T,L,S) :- S is the list of nodes of the binary tree T at level L Example in Haskell: Prelude>atlevel tree4 2 Prelude>[2,2]

Solution:

atlevel :: Tree a -> Int -> [a] atlevel t level = atlevel_iter t 1 where atlevel_iter Empty _ = [] atlevel_iter (Branch a left right) currentLevel = if currentLevel==level then [a] else if currentLevel > level then [] else (atlevel_iter left (currentLevel+1)) ++ (atlevel_iter right (currentLevel+1))

Another possibility is to decompose the problem:

levels :: Tree a -> [[a]] levels Empty = repeat [] levels (Branch a l r) = [a] : zipWith (++) (levels l) (levels r) atlevel :: Tree a -> Int -> [a] atlevel t n = levels t !! (n-1)

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

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:

tree64 = 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 )

Example in Haskell:

> layout tree64 Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...

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:

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:

tree65 = 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 )

Example in Haskell:

> layout tree65 Branch ('n',(15,1)) (Branch ('k',(7,2)) (Branch ('c',(3,3)) ...

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:

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?

Example in Haskell:

> layout tree65 Branch ('n',(5,1)) (Branch ('k',(3,2)) (Branch ('c',(2,3)) ...

Solution:

layout :: Tree a -> Tree (a, Pos) layout t = t' where (l, t', r) = layoutAux x1 1 t x1 = maximum l + 1 layoutAux :: Int -> Int -> Tree a -> ([Int], Tree (a, Pos), [Int]) layoutAux x y Empty = ([], Empty, []) layoutAux x y (Branch a l r) = (ll', Branch (a, (x,y)) l' r', rr') where (ll, l', lr) = layoutAux (x-sep) (y+1) l (rl, r', rr) = layoutAux (x+sep) (y+1) r sep = maximum (0:zipWith (+) lr rl) `div` 2 + 1 ll' = 0 : overlay (map (+sep) ll) (map (subtract sep) rl) rr' = 0 : overlay (map (+sep) rr) (map (subtract sep) lr) -- overlay xs ys = xs padded out to at least the length of ys -- using any extra elements of ys overlay :: [a] -> [a] -> [a] overlay [] ys = ys overlay xs [] = xs overlay (x:xs) (y:ys) = x : overlay xs ys

The auxiliary function is passed the x- and y-coordinates for the root of the subtree and the subtree itself. It returns

- a list of distances the laid-out tree extends to the left at each level,
- the subtree annotated with positions, and
- a list of distances the laid-out tree extends to the right at each level.

These distances are usually positive, but may be 0 or negative in the case of a skewed tree. To put two subtrees side by side, we must determine the least even separation so that they do not overlap on any level. Having determined the separation, we can compute the extents of the composite tree.

The definitions of `layout` and its auxiliary function use local recursion to compute the x-coordinates.
This works because nothing else depends on these coordinates.

## 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>