[Haskell-beginners] Tying the knot

[Patrick LeBoutillier]

Heinrich,

> A canonical example is the following solution to the problem of labeling all
> the leaves in a tree with the total leaf count:
>
>    data Tree a = Branch (Tree a) (Tree a) | Leaf a
>
>    labelLeaves :: Tree a -> Tree Int
>    labelLeaves tree = tree'
>        where
>        (n, tree') = label n tree  -- n is both result and argument!
>
>        label n (Branch a b) = (na+nb, Branch a' b')
>            where
>            (na,a') = label n a
>            (nb,b') = label n b
>        label n (Leaf _)     = (1, Leaf n)
>

This looks completely freaky to me... how does it work? Is it the
laziness that allows the sum to be calculated first while preserving
the structure (as thunks?), and then once the value of n is known it
is propagated back down the tree and the actual tree values
constructed? Anyways this is really amazing to my newbie eyes...

Patrick
-- 
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada