[Haskell-cafe] *GROUP HUG*

Yves Parès 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.
> -k
> --
> If I haven't seen further, it is by standing in the footprints of giants
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110525/051b6739/attachment.htm>

More information about the Haskell-Cafe mailing list