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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe