[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.)