Proposal: Exporting merge (was: Adding on)

[Christian Maeder]

Duncan Coutts schrieb:
> So start a new thread and lets try and find out if there is a consensus.
> 
> As an example variation from a program I wrote:
> 
> -- mergeBy cmp xs ys = (only_in_xs, in_both, only_in_ys)
> 
> mergeBy :: (a -> b -> Ordering) -> [a] -> [b] -> ([a], [(a, b)], [b])
> mergeBy cmp = merge [] [] []
>   where merge l m r []     ys     = (reverse l, reverse m, reverse (ys++r))
>         merge l m r xs     []     = (reverse (xs++l), reverse m, reverse r)
>         merge l m r (x:xs) (y:ys) = 
>           case x `cmp` y of
>             GT -> merge    l         m  (y:r) (x:xs)    ys
>             EQ -> merge    l  ((x,y):m)    r     xs     ys
>             LT -> merge (x:l)        m     r     xs  (y:ys)
> 
> It's rare of course that you need the generality of merging lists of
> different types. Though of course this also covers the slightly more
> common case of comparing where == is only an equivalence relation and
> you want to keep or combine both elements.

I've found the following generalization sufficient enough:

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


Add a parameter to join equal elements with the recursively merged list
tails. This allows to keep both or only one elements or to add
occurrences counts of multi-sets.

Cheers Christian