[Haskell-cafe] *GROUP HUG*
limestrael at gmail.com
Wed May 25 13:05:35 CEST 2011
So it seconds my initial point: you can't store the size because it has no
2011/5/25 Ketil Malde <ketil at malde.org>
> "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
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe