[Haskell-beginners] Tying the knot

Patrick LeBoutillier patrick.leboutillier at gmail.com
Wed Dec 29 23:52:32 CET 2010


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



More information about the Beginners mailing list