Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
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? <[email protected]>
Subject: Re: [Haskell-beginners] Cyclic structures
To: David Tchepak <[email protected]>
Cc: [email protected]
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 <[email protected]> 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
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 46, Issue 43
*****************************************
