[crntaylor]

I can't resist a quick plug for this beautiful O(n) implementation of the fibonacci sequence in Haskell. One line to define the list `fibs` -- an infinite list of fibonacci numbers -- and one line to define the function `fib` which simply takes the n'th element of the list.

    λ> let fibs  = 0 : 1 : zipWith (+) fibs (tail fibs)
    λ> let fib n = fibs!!n
    λ> fib 100
    354224848179261915075

[lccarrasco]

I really liked the haskell version when I first learned about it in a programming languages course, I believe I've never been more surprised than after seeing the output of 'take 10 fibs' without knowing how did that single line worked.

[taeric]

Correct me if I'm wrong, but this is also O(n) in space, right? I think you can get a similar scala version in:

    lazy val fib:Stream[BigInt] = 0 #::1 #:: fib.zip(fib.tail).map(x=>x._1+x._2)

This is neat and all, but the imperative version wins by being O(1) in space. Right?

[tmoertel]

No, the Haskell version will operate in constant space provided you don't hold onto the list:

    let fibs = 1 : 1 : zipWith (+) fibs (tail fibs) in fibs !! 100

Since the fibs list is visible only to the expression (fibs !! 100), and since the (!!) operator advances through the list discarding elements until it hits the 100th, those elements are free to be garbage collected. Further, since the elements of the list (after the first two) are generated only when consumed, only a few of the cons cells will ever be live at any point in time.

[taeric]

That makes sense, and I would think should be true in the Scala version as well. I did not know if it was, though. I guess I would have to spent a lot more time digging the details of the environment created to really see where the head of the list is dropped from scope.

Specifically, I would expect space to grow at O(n), but that it could be garbage collected quickly. The question is, how quickly would the garbage collector do its thing. Or are you saying that is dodged in the Haskell version, as well?

[FreeFull]

It is perfectly possible to write a fib function that takes O(1) space functionally too, but of course it'd have a worse time complexity due to the lack of memoisation.

[taeric]

Worse than O(n) for time complexity? Seems it should be easily doable to transcribe the straight forward iterative solution to a tail recursive one. Something like:

    (defun fib-help (a b curX desiredX)
                    (if (= curX desiredX)
                        b
                        (fib-help b (+ a b) (+ curX 1) desiredX)))

 
    (defun fib (x) (fib-help 0 1 1 x))

(No, I don't really know lisp that well... learning.)