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: fib x y = x : fib y (x+y) For example, fib 1 1 => [1,1,2,3,5,8,13,21,...]. Is there a reason why the canonical fib function is so complex? If not, would it be possible to use a simpler version in the tutorial? Thanks. -- Brian
The only reason the first version of fib was used in the Gentle Intro was to demonstrate recursive stream processing, and not to show a "canonical" version of Fibonacci. Indeed, the sentence preceeding it says: "For another example of the use of circularity, the Fibonacci sequence can be computed efficiently as the following infinite sequence: ...". Your proposed version is fine, and is similar to the "canonical" version that computes the nth Fibonacci number (as opposed to the entire stream) efficiently, but it does not demonstrate recursive streams. Hope this helps, -Paul 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:
fib x y = x : fib y (x+y)
For example, fib 1 1 => [1,1,2,3,5,8,13,21,...].
Is there a reason why the canonical fib function is so complex? If not, would it be possible to use a simpler version in the tutorial? Thanks.
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
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'.
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
participants (4)
-
Brian Berns -
Frank Seaton Taylor -
Jeffrey R Lewis -
Paul Hudak