Proposal: Add Data.List.sortNub and sortNubBy

[Christian Maeder]

Bulat Ziganshin schrieb:
> Hello Neil,
> 
> Tuesday, March 13, 2007, 12:38:14 PM, you wrote:
> 
>> Are we going to have dependency problems by making Data.List depend on
>> Data.Set? My guess is yes, but I'm not sure.
> 
> this is only an *implementation* dependency and it's ok as long as
> base includes both modules. if sometime in future situation will
> change, we can change implementation without boring users

In fact, as an implementation of sortNub/sortNubBy (if that is what we
want) I would rather suggest to generalize the merge function (i.e. as
below) for the mergesort algorithm (and possibly export merge, too).

Cheers Christian

merge :: (a -> a -> Ordering) -> (a -> a -> [a] -> [a]) ->  [a] -> [a]
-> [a]
merge cmp jn l1 l2 = case l1 of
    [] -> l2
    x1 : r1 -> case l2 of
        [] -> l1
        x2 : r2 -> let recmerge = merge cmp jn in case cmp x1 x2 of
             LT -> x1 : recmerge r1 l2
             EQ -> jn x1 x2 $ recmerge r1 r2
             GT -> x2 : recmerge l1 r2