Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Tying the knot (Antoine Latter)
----------------------------------------------------------------------
Message: 1
Date: Wed, 29 Dec 2010 22:08:29 -0500
From: Antoine Latter <aslat...@gmail.com>
Subject: Re: [Haskell-beginners] Tying the knot
To: aditya siram <aditya.si...@gmail.com>
Cc: Heinrich Apfelmus <apfel...@quantentunnel.de>,
beginners@haskell.org, haskell mailing list <haskell-c...@haskell.org>
Message-ID:
<aanlktim4mv93==0ohxut8ab_liwaf=h2cas0zeznc...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Wed, Dec 29, 2010 at 7:22 PM, aditya siram <aditya.si...@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.leboutill...@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@haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 30, Issue 48
*****************************************
