Composing maps?

[alexfmpe]

I was surprised that I couldn't find a Map composition function in containers. It seems it could be done with something no worse than O(n * log m), where n is the size of the initial/source map.

composition :: (Ord a, Ord b) => Map.Map b c -> Map.Map a b -> Map.Map a c
composition bc ab = flip Map.mapMaybe ab $ flip Map.lookup bc

[alexfmpe]

It's also possible to intersect on the b keys and b values. Everything here is linear except sortOn, so that gives O(n * log n + m) instead. Might matter if m is much larger than n

composition :: (Ord a, Ord b) => Map.Map b c -> Map.Map a b -> Map.Map a c
composition bc ab = Map.fromAscList $ fmap snd $ intersect
   (List.sortOn fst $ fmap (\(a,b) -> (b,a)) $ Map.assocs ab)
   (Map.assocs bc)
  where
    intersect :: Ord k => [(k,x)] -> [(k,y)] -> [(k, (x,y))]
    intersect kxs@((k,x):kxs') kys@((k',y):kys') = case k `compare` k' of
      GT -> intersect kxs kys'
      LT -> intersect kxs' kys
      EQ -> (k, (x,y)) : intersect kxs' kys'
    intersect _ _ = []

[treeowl]

The first option is quite natural. If I'm calculating right the second is never better. We have

• Complicated way:
  n log n + m
• Simple way:
  n log m
• Complicated minus simple:
  d = n log n + m - n log m
  = n log (n / m) + m

Let s = m / n, and substitute m = ns:

d = n log (1 / s) + n s
= n (log (1 / s) + s)
= n (-log s + s)

d is always positive when n is. In particular, Wolfram Alpha says that log (1/s) + s is always at least 1, and this plot shows that it gets much larger than that. That makes sense: when s is large, log s is negligible in comparison. When s is less than 1, log s goes negative so -log s goes positive. So your complicated version will perform considerably worse than your simple one.

[treeowl]

Conclusion: the first implementation is the correct one. But you should be able to tighten up the constraints a tad. In particular, we shouldn't need Ord a:

composition :: Ord b => Map.Map b c -> Map.Map a b -> Map.Map a c
composition bc ab = flip Map.mapMaybe ab $ flip Map.lookup bc

Please start a proposal on the libraries list; that will ensure the community likes the idea and help settle on a good name if so.

[alexfmpe]

Please start a proposal on the libraries list; that will ensure the community likes the idea and help settle on a good name if so.

Thanks for the feedback. Will do

[treeowl]

I haven't seen the proposal yet.

[jwaldmann]

for reference, this is the start of the mailing list discussion: https://mail.haskell.org/pipermail/libraries/2019-July/029731.html

[chshersh]

I think that having this compose function in the containers library is a good thing! In terms of the performance, you can have a composable interface around Map with fast lookups, but you need to sacrifice the ability to traverse the resulting Map. So something like this is possible:

mapToKleisli :: Ord k => Map k v -> Kleisli Maybe k v
mapToKleisli m = Kleisli (\k -> Map.lookup k m)

Where Kleisli is defined in base. And now compose for this Kleisli is just >>> or <<< from the Category typeclass. Not sure it's worth mentioning in the documentation, just a compelling use case, how abstractions from the standard library allow to reuse data types and provide an alternative implementations 🙂

[sjakobi]

Can this be closed now that #672 has been merged?

[alexfmpe]

It seems it could be done with something no worse than O(n * log m), where n is the size of the initial/source map.

It just hit me that the simple implementation actually matches the asymptotic lower bound.

n :: Map a b
m :: Map b c
m `compose` n :: Map a c

Given there's |n| entries in the first map, the composition essentially maps each a in n to Maybe c (the composed lookup yields either one of the c in m or Nothing).
The number of possible such mappings is (|m| + 1) ^ |n|.

Now we can do an information theory reasoning similar to the one for the lower bound of sorting: https://cs.stackexchange.com/questions/32311/proving-the-lower-bound-of-compares-in-comparison-based-sorting/35229#35229

To distinguish between x possible values, we need ceil (log (x)) bits .
Thus, we have a lower bound of log ((|m| + 1) ^ |n|) = |n| * log (|m| + 1) bits.

Data.Map lookups are comparison-based, and each comparison gives us at most one bit of information: in the worst case we'll always be left with at least half of the remaining possible values, meaning we need at least as many comparisons as we need bits.

I'd like to put this info near the code, but I'm also reluctant of adding a big block of text to 4 different implementations (strict/lazy, poly/int).
Is there a way to put the explanation in one place and link to it somehow from haddocks in the implementations?

[alexfmpe]

I'd like to put this info near the code, but I'm also reluctant of adding a big block of text to 4 different implementations (strict/lazy, poly/int).

We don't have the strict variants anymore, and IntMap works differently, so I just went for it in #960