Difference between revisions of "99 questions/61 to 69"
m (solution to prob. 61A) |
RossPaterson (talk | contribs) (rename Nil to Empty, and tweak P61A) |
||
| Line 5: | Line 5: | ||
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. |
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. |
||
| + | == Binary trees == |
||
| − | |||
| + | |||
| + | The type of binary trees: |
||
| + | <haskell> |
||
| ⚫ | |||
| + | deriving (Show, Eq) |
||
| + | </haskell> |
||
| + | An example tree: |
||
| + | <haskell> |
||
| ⚫ | |||
| + | (Branch 2 Empty Empty) |
||
| + | </haskell> |
||
| + | |||
== Problem 61 == |
== Problem 61 == |
||
| Line 17: | Line 29: | ||
Example in Haskell: |
Example in Haskell: |
||
| + | > count_leaves tree1 |
||
| − | > count_leaves (Branch 1 (Branch 2 Nil (Branch 4 Nil Nil)) (Branch 2 Nil Nil)) |
||
2 |
2 |
||
</pre> |
</pre> |
||
| Line 23: | Line 35: | ||
Solution: |
Solution: |
||
<haskell> |
<haskell> |
||
| ⚫ | |||
| ⚫ | |||
| + | count_leaves (Branch a Empty Empty) = 1 |
||
| − | |||
| − | count_leaves |
+ | count_leaves (Branch a left right) = count_leaves left + count_leaves right |
| ⚫ | |||
| ⚫ | |||
</haskell> |
</haskell> |
||
| Line 41: | Line 51: | ||
Example in Haskell: |
Example in Haskell: |
||
| + | > leaves tree1 |
||
| ⚫ | |||
| + | [4, 2] |
||
| − | [Branch 4 Nil Nil, Branch 2 Nil Nil] |
||
</pre> |
</pre> |
||
Solution: |
Solution: |
||
<haskell> |
<haskell> |
||
| − | leaves |
+ | leaves :: Tree a -> [a] |
| − | leaves |
+ | leaves Empty = [] |
| − | leaves (Branch a |
+ | leaves (Branch a Empty Empty) = [a] |
| ⚫ | |||
</haskell> |
</haskell> |
||
| − | |||
| − | |||
== Problem 62 == |
== Problem 62 == |
||
Revision as of 23:48, 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.
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)
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
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
Problem 62
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 62B
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 63
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 64
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 65
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 66
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 67
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 68
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 69
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>