9 Oct
2006
9 Oct
'06
2:26 p.m.
Yang wrote:
But laziness will cause this to occupy Theta(n)-space of cons-ing thunks.
No, it doesn't. Insisting on accumulator recursion does. Actually, using reverse does. Think about it, a strict reverse cannot use less than O(n) space, either.
Well, in general, the problem you run into is this, where we use linear space for the thunks:
foldl (+) 0 [1,2,3] [etc.]
The point is that the claim "in general" is wrong. The problem arises for the special case (fold (+) 0) but things are different in your special case addPoly1. Regards, apfelmus