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

apfelmus at quantentunnel.de apfelmus at quantentunnel.de
Mon Oct 9 10:26:13 EDT 2006

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.


More information about the Haskell-Cafe mailing list