[Haskell-cafe] [Haskell-beginners] Tying the knot
aslatter at gmail.com
Thu Dec 30 04:08:29 CET 2010
On Wed, Dec 29, 2010 at 7:22 PM, aditya siram <aditya.siram at gmail.com> wrote:
> 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.
Once when I was parsing a group of source files into an AST, the
source files included 'copy' directives that allowed pieces of syntax
to be a clone of some other piece of syntax - even across source
So I did the whole process of parsing in the Reader monad, which was
parametrized over the result of parsing all of the files. When I hit a
copy directive, I simply called 'ask' and looked up the element I
wanted to copy.
It doesn't allow for separate processing of source files, but I didn't
really need it.
> First forget about 'labelLeaves' and think a function that only
> returned the leaf count:
> count :: Tree a -> Int
> count tree = c
> c = count' tree
> count' (Branch a b) = na+nb
> na = count' a
> nb = count' b
> count' (Leaf _) = 1
>> count $ Branch (Leaf "hello") (Leaf "world")
> 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'
> (0x0000, tree') = label 0x0000 tree -- n is both result and argument!
> label 0x0000 (Branch a b) = (na+nb, Branch a' b')
> (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))
> On Wed, Dec 29, 2010 at 4:52 PM, Patrick LeBoutillier
> <patrick.leboutillier at gmail.com> wrote:
>>> 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'
>>> (n, tree') = label n tree -- n is both result and argument!
>>> label n (Branch a b) = (na+nb, Branch a' b')
>>> (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 LeBoutillier
>> Rosemère, Québec, Canada
>> Beginners mailing list
>> Beginners at haskell.org
> Beginners mailing list
> Beginners at haskell.org
More information about the Haskell-Cafe