How can I union maps of different types in Haskell?

user_4575363 0
Viewed 209

I'm looking for a Haskell function that combines two Maps of different types. I.e. something like

mergeWith :: (a -> b -> c) -> Map k a -> Map k b -> Map k c

I want it to behave like an inner join in SQL.

unionWith doesn't cut it since it requires both Maps to have values of the same type.

Is there such a function? If not, what's the most efficient way to implement it?

haskell
2 Answers

Does intersectionWith not fit the bill?

Admin1

This was the best that I could do myself

import qualified Data.Map.Strict as M

mergeWith :: (Ord k) => (a -> b -> c) -> M.Map k a -> M.Map k b -> M.Map k c
mergeWith f m1 m2 = M.fromList $ g (M.toList m1) (M.toList m2)
  where
    g [] _ = []
    g _ [] = []
    g m1'@((k1, v1):_) m2'@((k2, v2):_)
      | k1 < k2   = g (tail m1') m2'
      | k1 > k2   = g m1' (tail m2')
      | otherwise = (k1, f v1 v2) : g (tail m1') (tail m2')

It sholud have O(n) complexity where n is the size of the bigger Map

user_45753630
Related