2 ms·
I've never written a line of python in my life, so I'm interested in how this "recursive function" can do anything different on each recursive call if it takes
by louthy 2y ago
I've never written a line of python in my life, so I'm interested in how this "recursive function" can do anything different on each recursive call if it takes no arguments?
def ints():
yield 1
yield from map(lambda x: x + 1, ints())
Surely it would always yield a stream of `1`s? Seems very weird to my brain. "As simple as that" it is not!
- rowanG077 2y agoSure it yields 1. But then it adds one to each yield form the recursive call. And repeat.
- lalaithion 2y agoThe first item yielded from ints() is 1. For the second item, we grab the first item from ints(), and then apply the map operation, and 1+1 is 2. For the third item, we grab the second item from ints(), and then apply the map operation, and 1+2 is 3.
- louthy 2y agoGot it, thanks! The syntax was throwing me a bit there.
- lalaithion 2y agoIt’s a pretty bad system since it takes O(n^2) time to produce n integers but ¯\_(ツ)_/¯. Haskell avoids the extra cost by immutable-self-reference instead of creating a new generator each time.
- tomsmeding 2y agoEDIT: 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.
- deleted 2y ago[deleted]
- mrkeen 2y agoWhen 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 2y agoInteresting! 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 2y agoI 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 2y agoOh for sure, I was talking about the internal representation on the heap. The user program sees none of this. :)