[Haskell-cafe] Lists concatenation being O(n)

Jake McArthur jake.mcarthur at gmail.com
Thu Oct 13 22:38:55 CEST 2011

On Thu, Oct 13, 2011 at 3:32 PM, Yves Parès <limestrael at gmail.com> wrote:
>> The number of new cons cells created in due course is Θ(length xs). These
>> cons cells would not have been created if we printed length xs and printed
>> length ys separately.
> Okay, so the major problem comes from memory management.

Well, it comes from extra allocations. Since most values are
immutable, most Haskell work is in the form of allocations.

- Jake

More information about the Haskell-Cafe mailing list