99 questions/61 to 69
From HaskellWiki
RossPaterson (Talk  contribs) (rename Nil to Empty, and tweak P61A) 
RossPaterson (Talk  contribs) (solution for P64) 

Line 122:  Line 122:  
== Problem 64 == 
== Problem 64 == 

−  <Problem description> 
+  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 uses a layout strategy in which 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. 

−  <pre> 
+  Here is an example tree for this problem and the following two: 
−  Example: 
+  <haskell> 
−  <example in lisp> 
+  tree2 = Branch 'n' 
−  +  (Branch 'k' 

−  Example in Haskell: 
+  (Branch 'c' 
−  <example in Haskell> 
+  (Branch 'a' Empty Empty) 
−  </pre> 
+  (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 

+  ) 

+  </haskell> 

Solution: 
Solution: 

<haskell> 
<haskell> 

−  <solution in haskell> 
+  type Pos = (Int, Int) 
−  </haskell> 

−  <description of implementation> 
+  layout :: Tree a > Tree (a, Pos) 
+  layout t = fst (layout 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 

+  </haskell> 

+  The auxiliary function is passed the xcoordinate for the leftmost node of the subtree, the ycoordinate for the root of the subtree, and the subtree itself. 

+  It returns the subtree annotated with positions, plus the count of <tt>Branch</tt> nodes in the subtree. 

== Problem 65 == 
== Problem 65 == 
Revision as of 00:28, 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 uses a layout strategy in which 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 an example tree for this problem and the following two:
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 (layout 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 xcoordinate for the leftmost node of the subtree, the ycoordinate 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
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
9 Problem 66
<Problem description>
Example: <example in lisp> 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>