Discussion on: [Discuss] What's your favourite Fibonacci implementation and in which language? Mine is in Haskell

[Rebecca Skinner]

The zipWith implementation is a canonical example of a performant solution that makes good use of haskell's laziness and terseness. That said, there are a couple of fun variations that I think are nice to look at.

First: I think it's always fun to point out that there's a closed-form solution:

closedForm :: Integer -> Integer
closedForm idx =
  let
    phi :: Double
    phi = (1.0 + sqrt 5.0) / 2.0
    numerator = phi ** fromIntegral idx
    denominator = sqrt 5.0
  in floor $ (numerator / denominator) + (1/2)

fibs = map closedForm [0..]

This is only accurate up to around the 25th Fibonacci number because of floating point errors, but it can be fun to use when conversations about how to calculate it come up.

Second: I think it's fun to point out that (->) has an Applicative instance that you can use:

fibs = 0 : 1 : (zipWith (+) <*> tail) fibs

or in a slightly less terse style

fibs =
  let
    next = zipWith (+) <*> tail
  in
    0 : 1 : next fibs

I'm not sure either of these is a "best" or "favorite" solution, since that's going to be highly dependent on what your specific need is, but I think each of them provides some enlightening information.

[PatrickBuhagiar]

Thanks for sharing Rebecca, I've actually learnt something new today about how to use <*>.

fibs = 0 : 1 : (zipWith (+) <*> tail) fibs

It's very neat, I like it!