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

[Will Ness]

Derek Elkins <derek.a.elkins <at> gmail.com> writes:

> 
> On Sun, Jan 17, 2010 at 2:22 PM, Will Ness <will_n48 <at> yahoo.com> wrote:
> > Hello cafe,
> >
> > I wonder, if we have List.insert and List.union, why no List.merge (:: Ord 
a =>
> > [a] -> [a] -> [a]) and no List.minus ? These seem to be pretty general
> > operations.
> 
> Presumably by List.minus you mean the (\\) function in Data.List. 

No, it has to search its second list over and over from the start, to be able 
to deal with unordered lists, so its performance can't be good. 


> You
> probably also want to look at the package data-ordlist on hackage
> (http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/Data-
OrdList.html)
> which represents sets and bags as ordered lists and has all of the
> operations you mention.


I did, thanks again! Although, that package deals with non-decreasing lists, 
i.e. lists with multiples possibly. As such, its operations produce non-
decreasing lists, i.e. possibly having multiples too. 

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.

I guess the first variety is more appropriate for bags, and the second one - 
for sets. The two would have to be de-conflated for that. (?)