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

[Derek Elkins]

On Wed, Jan 20, 2010 at 9:42 AM, Will Ness <will_n48 at yahoo.com> wrote:
> 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.

Then use the ordlist one.

>> 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.

It is clear that some of the operations are guaranteed to produce sets
given sets.  The documentation could be better in this regard though.

> 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.

The 'union' and 'minus' functions of ordlist meet this requirement if
you satisfy the preconditions.