3 ms·
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 5000005
by mrkeen 2y ago
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 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. :)