Will Ness schrieb:
Christian Maeder
writes: Will Ness schrieb:
I meant strictly increasing ordered lists, without multiples, for which the two operations, 'merge' and 'minus', would also have to produce like lists, i.e strictly increasing, without multiples. Why don't you use directly Data.Set?
It says it's based on size balanced Trees? I initially wondered why no such fundamental operations as merge and minus for _lists_, in the stadard libraries?
Yes, balanced trees, which makes insertion and member testing O(log n).
Also, its to/from list conversions are O(n), so probably won't work for infinite lists.
One should not convert much from and to list, but always use operations on sets directly. Sets are finite. I wonder what fundamental advantage there is for infinite strictly increasing lists.
I was told the trend is to move specifics to hackage packages, but I wonder why shouldn't such fundamental operations be just included in standard Data.List?
Both the current "Set" operations of Data.List and the (so many) functions from Data.Ordlist are only useful for short lists (or other special purposes) because of efficiency. Furthermore, there is some risk that the invariant of lists being (strictly) sorted is violated by accident (programming-error). The ...By-functions allow to further confuse orders.
There are also bags aka multisets: http://hackage.haskell.org/package/multiset
it's too seems to be based on trees.
Yes.
Data.Ordlist seems to be a good match, except for its conflation of ascending/non-decreasing lists under one "ordered" category (i.e. sets/bags distinction).
If you say, these should be two separate module, I would agree. Cheers Christian