# Difference between revisions of "99 questions/54A to 60"

(Solve P54A) |
(Solve P55) |
||

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) |
+ | data Tree a = Leaf | Branch a (Tree a) (Tree a) deriving Show |

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

Line 27: | Line 27: | ||

== Problem 55 == |
== Problem 55 == |
||

− | <Problem description> |
||

+ | (**) 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: |
Example: |
||

− | <example in lisp> |
||

⚫ | |||

+ | * 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 |
||

+ | </pre> |
||

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

− | <example in Haskell> |
||

+ | <pre> |
||

+ | *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)] |
||

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

Solution: |
Solution: |
||

<haskell> |
<haskell> |
||

− | <solution in haskell> |
||

+ | cbalTree 0 = [Leaf] |
||

+ | 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> |
</haskell> |
||

− | <description of implementation> |
||

+ | 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 == |

## Revision as of 20:17, 13 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.

## 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 = Leaf | Branch a (Tree a) (Tree a) deriving Show
```

```
Tree a
```

## 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' 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)]

Solution:

```
cbalTree 0 = [Leaf]
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.

## Problem 56

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 57

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 58

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

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