Personal tools

99 questions/61 to 69

From HaskellWiki

< 99 questions(Difference between revisions)
Jump to: navigation, search
(moved p70)
m (solution 61)
Line 8: Line 8:
 
== Problem 61 ==
 
== Problem 61 ==
   
<Problem description>
+
Count the leaves of a binary tree
  +
  +
A leaf is a node with no successors. Write a predicate count_leaves/2 to count them.
   
 
<pre>
 
<pre>
 
Example:
 
Example:
<example in lisp>
+
% count_leaves(T,N) :- the binary tree T has N leaves
   
 
Example in Haskell:
 
Example in Haskell:
<example in Haskell>
+
> count_leaves (Branch 1 (Branch 2 Nil (Branch 4 Nil Nil)) (Branch 2 Nil Nil))
  +
2
 
</pre>
 
</pre>
   
 
Solution:
 
Solution:
 
<haskell>
 
<haskell>
<solution in haskell>
+
data Tree a = Nil | Branch a (Tree a) (Tree a)
</haskell>
 
   
<description of implementation>
+
count_leaves Nil = 0
  +
count_leaves (Branch a Nil Nil) = 1
  +
count_leaves (Branch a left right) = count_leaves left + count_leaves right
  +
</haskell>
 
 
 
== Problem 61A ==
 
== Problem 61A ==

Revision as of 12:51, 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.


1 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 (Branch 1 (Branch 2 Nil (Branch 4 Nil Nil)) (Branch 2 Nil Nil))
2

Solution:

data Tree a = Nil | Branch a (Tree a) (Tree a)
 
count_leaves  Nil                  = 0
count_leaves (Branch a Nil  Nil)   = 1
count_leaves (Branch a left right) = count_leaves left + count_leaves right

2 Problem 61A

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

3 Problem 62

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

4 Problem 62B

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

5 Problem 63

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

6 Problem 64

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

7 Problem 65

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

8 Problem 66

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

9 Problem 67

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

10 Problem 68

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

11 Problem 69

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>