[tomsmeding]

EDIT: Wrong, the Haskell code is linear. See child comments.

The extra cost is not in the recursive calls, of which there is only one per returned number. The cost is in achieving a yielded value n by starting with 1 and adding 1 to it (n-1) times. The given Haskell code:

ints = 1 : map (+1) ints

has the exact same problem, and it's just as quadratic. It might have a somewhat better constant factor, though (even apart from Python being interpreted) because there's less function calls involved.

[mrkeen]

When in doubt, measure!

Your code didn't show a quadratic blowup in the timing:

  main = print . sum $ take 1000000 ints
  ints = 1 : map (+1) ints

  500000500000
  real    0m0.022s
  user    0m0.021s
  sys     0m0.000s

[tomsmeding]

Interesting! My intuition was wrong. I neglected to fully appreciate that the list is memoised.

What's happening, if I'm not mistaken, is that the unevaluated tail of the list is at all times a thunk that holds a reference to the cons cell holding the previous list item. Hence this is more like `iterate (+1) 1` than it seems at first glance.

[lgas]

I am fairly certain lists in Haskell are just normal singly linked lists with pointers pointing to the next item in the list. There's no need to maintain a reference to the previous cell. The last cell in any infinite list (or any finite list that hasn't been fully evaluated) will be an unevaluated thunk but that's not really observable to the program/programmer.

[tomsmeding]

Oh for sure, I was talking about the internal representation on the heap. The user program sees none of this. :)