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: Cyclic structures (Chadda? Fouch?)
----------------------------------------------------------------------
Message: 1
Date: Wed, 25 Apr 2012 13:52:52 +0200
From: Chadda? Fouch? <chaddai.fou...@gmail.com>
Subject: Re: [Haskell-beginners] Cyclic structures
To: David Tchepak <tche...@gmail.com>
Cc: beginners@haskell.org
Message-ID:
<canfjzrzn78raka3twifht5o8xtd3b2rrj9g77+7myvxnxdv...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Mon, Apr 23, 2012 at 8:00 AM, David Tchepak <tche...@gmail.com> wrote:
>
> ? ones = forever 1
> ? forever x = x : forever x
So forever 1 is a list whose first element is 1 and the tail is
forever 1, which itself is a list whose head is 1 and the tail is
forever 1...
> The book then has a re-written version of `forever` that looks like this:
>
> ? forever x = zs
> ? ? where zs = x : zs
>
So explicitly, forever 1 is a list called zs whose head is 1 and whose
tail is zs itself.
While both code describe the same list, in the second case the sharing
between the list itself and its head is made explicit ("zs = x : zs"
is recursive data) while in the first, you have a recursive function
where the sharing is not explicit : the default with a recursive
function is to evaluate it and recursively evaluate the calls to
itself in the body of the function, there's no reason to think the
result of the recursive call is the same as the main call... Here of
course this is the case, but to automatically recover the sharing is
only an optimisation in certain cases, in some others it is in fact a
catastrophe :
> stuff n = (sum [1..n], length [1..n])
Here the naive version will work in constant memory while the version
where the sharing was recovered ( let xs = [1..n] in (sum xs, length
xs) ) will take O(n) memory...
In other words, GHC is very cautious about recovering sharing, so if
you want it you better be explicit about it by giving yourself a name
to the shared part like in the second version of forever.
--
Jeda?
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 46, Issue 43
*****************************************
