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. scanl and infinite sequences [scanl for Fibonacci sequences]
(Seung)
2. Re: scanl and infinite sequences [scanl for Fibonacci
sequences] (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Tue, 25 Jan 2011 01:57:25 +0000 (UTC)
From: Seung Soo, Ha <sungs...@gmail.com>
Subject: [Haskell-beginners] scanl and infinite sequences [scanl for
Fibonacci sequences]
To: beginners@haskell.org
Message-ID: <loom.20110125t024847-...@post.gmane.org>
Content-Type: text/plain; charset=us-ascii
I was playing with the project Euler problems and found heaps of
Fibonacci generating codes in Haskell.
One caught my eye:
fib = 1 : scanl (+) 1 fib ....(1)
when my understanding was limited to
"folds just replace : with the function you provide
scans show all the intermediate states of your fold"
this line of code was very easy to understand.
Efficient too(according to the wiki article on Haskell)
But now that I'm trying to grasp foldl and foldr, I no longer understand that
line of code!!!
This is especially confusing, as afaik, (1) is generating an infinite list but
I thought you can't use foldl for infinite lists!
Tried replacing scanl with scanr
(foldr is supposed to work with infinite lists right?)
fib = 1 : scanr (+) 1 fib .....(2)
somewhat surprisingly, (2) crashes.
I've read numerous articles on folds on the haskell wiki, and also this
stack overflow post (http://stackoverflow.com/questions/3082324)
Just as I thought I was getting a hold on the concept of folds... This..
What am I missing here?
------------------------------
Message: 2
Date: Tue, 25 Jan 2011 11:13:59 +0100
From: Daniel Fischer <daniel.is.fisc...@googlemail.com>
Subject: Re: [Haskell-beginners] scanl and infinite sequences [scanl
for Fibonacci sequences]
To: beginners@haskell.org
Cc: "Seung Soo, Ha" <sungs...@gmail.com>
Message-ID: <201101251114.00376.daniel.is.fisc...@googlemail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Tuesday 25 January 2011 02:57:25, Seung Soo, Ha wrote:
> I was playing with the project Euler problems and found heaps of
> Fibonacci generating codes in Haskell.
> One caught my eye:
>
> fib = 1 : scanl (+) 1 fib ....(1)
>
> when my understanding was limited to
> "folds just replace : with the function you provide
> scans show all the intermediate states of your fold"
The intermediate states of the fold are the fold applied to an initial
segment of the list.
foldl f z xs = last scanl f z xs
For an infinite list, scanl produces an infinite list too, so there's no
last, hence we see that foldl doesn't work on infinite lists.
> this line of code was very easy to understand.
> Efficient too(according to the wiki article on Haskell)
>
> But now that I'm trying to grasp foldl and foldr, I no longer understand
> that line of code!!!
>
> This is especially confusing, as afaik, (1) is generating an infinite
> list but I thought you can't use foldl for infinite lists!
> Tried replacing scanl with scanr
> (foldr is supposed to work with infinite lists right?)
>
> fib = 1 : scanr (+) 1 fib .....(2)
>
> somewhat surprisingly, (2) crashes.
Not surprising. scanr 'works from the right', the intermediate states are
the results of the fold on the trailing segments of the list. If the list
is infinite, the trailing segments are infinite too, it can only produce a
result if the combining function is lazy in its second argument (that is
also the case for foldr). (+) is strict, hence it doesn't work.
>
> I've read numerous articles on folds on the haskell wiki, and also this
> stack overflow post (http://stackoverflow.com/questions/3082324)
> Just as I thought I was getting a hold on the concept of folds... This..
>
> What am I missing here?
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 31, Issue 30
*****************************************
