[Haskell-cafe] Re: Why no merge and listDiff?

[Christian Maeder]

Will Ness schrieb:
> Christian Maeder <Christian.Maeder <at> dfki.de> 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