[Haskell-cafe] Re: Haskell performance (again)!

[apfelmus at quantentunnel.de]

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