Simpler Fibonacci function

[Frank Seaton Taylor]

On Tuesday, February 5, 2002, at 02:16 , Jeffrey R Lewis wrote:

> On Tuesday 05 February 2002 09:40 am, Brian Berns wrote:
>> I am new to functional programming and teaching myself Haskell.  The
>> canonical Haskell "fib" function (e.g. as presented in the "Gentle"
>> tutorial) is:
>>
>>    fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]
>>
>> This seems, to be polite, a bit overly complex.  By comparison, here
>> is a simpler version:
>
> As an aside, here's a nicer way of writing the stream version of fib:
>
>     fib = 1 : 1 : [ a + b | a <- fib | b <- tail fib ]
>
> This gets rid of the distraction of the zip and the pair, letting you 
> see
> the simple structure of the definition more clearly.
>
> This, however, is not Haskell 98 (the use of multiple generators 
> separated
> by `|').  But it is supported by both GHC and Hugs (using flag -98).  
> See
> the sections in the user manuals under `parallel list comprehensions'.
>
> --Jeff
> http://www.haskell.org/mailman/listinfo/haskell

And while you're at it start the sequence with 0 : 1 : ... so that it 
has the nice property that:

   gcd (fib !! m) (fib !! n) == fib !! (gcd m n)

--
Frank Seaton Taylor
fstaylo@alpha.ncsc.mil