[Haskell-cafe] *GROUP HUG*

Ketil Malde ketil at malde.org
Wed May 25 10:15:32 CEST 2011

"Richard O'Keefe" <ok at cs.otago.ac.nz> 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.

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

More information about the Haskell-Cafe mailing list