## Arboreal Haskell

(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.