Re: [Haskell-cafe] *GROUP HUG*

So it seconds my initial point: you can't store the size because it has no sense. 2011/5/25 Ketil Malde

"Richard O'Keefe" writes:

...

...

Then tell me, why does calculating the length of a (Haskell) list has O(n) complexity.

...

Because it is a rather rare operation and the cost of doing this would be far higher than you think.

I suspect that if you store the length non-strictly, it would build up thunks, causing a stack overflow when evaluated. If it is strict, it would make a lot of operations that are O(1) today into O(n) operations.

-k -- If I haven't seen further, it is by standing in the footprints of giants

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe