[thyrsus]

I'm a python newby, so please correct the following: The first function looks quadratic in time and linear in stack space, while the second function looks linear in time and constant in stack space. Memoizing would convert the first function to linear in time and linear in space (on the heap instead of the stack). For python, wouldn't I always use the second definition? For Haskell, I would use the [1..] syntax which the compiler would turn into constant space linear time machine code.

[trealira]

Late response, but yes, you are completely right. You wouldn't use either implementation whether you're using Python or Haskell; you'd use what you said, because that's both the most obvious and the most performant method of achieving the goal. It's just a fun exercise to show that the version using a lazy map is equivalent to the obvious thing. Some people find it mind-bending and satisfying in the same way some people might find bit-twiddling hacks cool, or math nerds might find any of these mathematical identities cool.

https://math.stackexchange.com/questions/505367/collection-o...