Given
data Tree a = Leaf a | Node (Tree a) (Tree a)
Write a leaf counter.
Hutton suggests:
leaves :: Tree a -> Int
leaves (Leaf _) = 1
leaves (Node l r) = leaves l + leaves r
I tried:
leavesTrent :: Tree a -> Int
leavesTrent = leaves' 0
where
leaves' n (Leaf a) = n + 1
leaves' n (Node l r) = (leaves' n l), (leaves' n r)
The idea is:
If it is a leaf, add one to the accumulator. (Following Hutton's explanation of how sum works if defined with foldl.) If it is a tree, proceed down the left subtree recursively, until you get to a leaf, then roll up to the right subtree. The problem (among the problems) is that I don't know how to tell the compiler to do all lefts, before backing up to go right. I only know how to do that using a real operator like "+" or foo (l, r).
Is that kind of no-op recursive branching possible?
Trent.