[Haskell-beginners] Tying the knot

[Antoine Latter]

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

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.

Antoine

> 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
> <patrick.leboutillier at gmail.com> wrote:
>> 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>