My brain turns into strange braid when I see this kind of thing. I don't quite understand it and I've never used it in real world code but I'll try and explain anyway. Caveat emptor. First forget about 'labelLeaves' and think a function that only returned the leaf count: count :: Tree a -> Int count tree = c where c = count' tree count' (Branch a b) = na+nb where na = count' a nb = count' b count' (Leaf _) = 1
count $ Branch (Leaf "hello") (Leaf "world") 2
Now look at 'n' and imagine it was a memory location. Mentally
substitute some hex address (like 0x0000) if it makes it easier.
Here's what the function looks like now:
labelLeaves :: Tree a -> Tree Int
labelLeaves tree = tree'
where
(0x0000, tree') = label 0x0000 tree -- n is both result and argument!
label 0x0000 (Branch a b) = (na+nb, Branch a' b')
where
(na,a') = label 0x0000 a
(nb,b') = label 0x0000 b
label 0x0000 (Leaf _) = (1, Leaf 0x0000)
So if labelLeaves is given (Branch (Leaf "hello") (Leaf "world")) as
an argument, and we continue to think of 'n' as a memory location the
function returns something like:
(Branch (Leaf 0x0000) (Leaf 0x0000))
The part of the function where the leaves are counted up is exactly
like my 'count' example above, but when the function is done instead
of just returning it this line:
(n,tree') = label n tree
assigns the final count to 'n'. If 'n' is a memory location the final
leaf count would be sitting in 0x0000. Subbing the value at that
location into the result we get:
(Branch (Leaf 2) (Leaf 2))
-deech
On Wed, Dec 29, 2010 at 4:52 PM, 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
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners