[Haskell-beginners] scanl and infinite sequences [scanl for Fibonacci sequences]

[Daniel Fischer]

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?