# Proposal: Exporting merge (was: Adding on)

Christian Maeder maeder at tzi.de
Mon Nov 6 07:16:15 EST 2006

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