[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?