(Chapter 7 of The Haskell School of Expression is about trees.)
The first definition is of a tree with values stored only at the leaves, i.e.
data Tree a = Leaf a | Branch (Tree a) (Tree a)
It then gives a mapTree function (equivalent to map on a list), which is trivial, and functions fringe, treeSize and treeHeight, which return respectively the list of the leaf values, the number of leaves, and the max depth. In the text, these are defined in the usual recursive way. An exercise is to write a Tree equivalent of the fold function for lists. Which I think I managed:
foldTree :: (a -> b -> b) -> (b -> b -> b) -> b -> Tree a -> b
foldTree fLeaf _ init (Leaf x) = fLeaf x init
foldTree fLeaf fBranch init (Branch x y) = fBranch x' y'
where x' = foldTree fLeaf fBranch init x
y' = foldTree fLeaf fBranch init y
The trick was in recognising that I needed two functions, one for dealing with leaves and the other for dealing with branches (because (:) is a different type from (++) and both are used in fringe). Of course, the performance implication of all those list appends makes me think that in the real world, I’d write fringe using only (:):
fastFringe :: Tree a -> [a]
fastFringe t = acc t []
where acc (Leaf x) l = x : l
acc (Branch x y) l = acc x (acc y l)
(It also occurs to me that fringe is more usually called flatten IME). The next exercises involved trees with internal values (not at the leaves), i.e.
data InternalTree a = ILeaf
| IBranch a (InternalTree a) (InternalTree a)
This is a bit more like way I’m used to trees working, and the exercises were easier. InternalTree versions of zipWith and zip (defined in terms of zipWith of course) were easy, as were versions of take and takeWhile. I was impressed with the “magic” of the InternalTree version of repeat:
repeatInternalTree :: a -> InternalTree a
repeatInternalTree a = t
where t = (IBranch a (t) (t))
There are two bits of magic here. First, this is an infinitely recursive definition. Haskell uses lazy evaluation, so this is designed to be used with takeTree or takeTreeWhile. The second piece of magic: where is the base case constructor (ILeaf) specified? It isn’t! Yet
takeTree 2 (repeatInternalTree 5)
returns
IBranch 5 (IBranch 5 ILeaf ILeaf) (IBranch 5 ILeaf ILeaf)
as hoped for, if not quite expected. The only thing I’m not really grokking right now are the InternalTree versions of foldr and possibly foldl (and possibly a third type of fold). I’ve got a feeling there is some higher-order function extractable that controls pre-, post-, or in-order node traversal on InternalTree, but I’m unsure of the structural differences of foldl and foldr when applied to trees. I am also puzzling a bit over the semantics of zipWith and zip when applied to trees with only leaf-node values.
PS. Gleep = glorp.