> In Haskell, the reason for not doing this (besides simplicity, and inertia) > actually is (I think) laziness: you don't want to evaluate > the "length" field of the second argument of the "cons" prematurely.
Yes, this is what I meant. I shouldn't have spoken about complexity, it was irrelevant as you pointed it out. 2011/5/24 Johannes Waldmann <waldm...@imn.htwk-leipzig.de> > Yves Parès <limestrael <at> gmail.com> writes: > > > For instance, one of my friends asked me once why the operation of > > calculating the length of list has an O(n) complexity, > > since to his opinion, you could just store the size inside the list > > and increment it when elements are appended. > > Then tell me, why does calculating the length of a (Haskell) > list has O(n) complexity. > > I could just store the length of the list - as an additional argument > to the "Cons" constructor that is automatically initialized on construction > (and you never need to change it later, since Haskell objects > are "immutable", in the words of Java programmers) > > In Haskell, the reason for not doing this (besides simplicity, and inertia) > actually is (I think) laziness: you don't want to evaluate > the "length" field of the second argument of the "cons" prematurely. > > Well, unless you look at the "length" field of the constructed object, > it won't be evaluated, but a pile of thunks will be constructed instead, > and I think that's what you really want to avoid. > > On the other hand, there are implementations of strict sequences > with an O(1) size implemenation. > > http://hackage.haskell.org/packages/archive/containers/0.4.0.0/doc/html/Data-Sequence.html#v:length > > J.W. > > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe