+0.9 we can have it

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

Which has O(|ab| * log |bc|) performance.

The given implementation traverses all of ab even if bc is empty. We could detect this. But for |bc| = 1, there is no work-around? So, O(|ab| * max(1, log |bc|)) ? I think this could only be improved if we had a representation of the inverse of ab as well. I don't think it should be computed on-the-fly, as in https://github.com/haskell/containers/issues/647#issuecomment-504798611 This would better be handled in a proper library for relations ( https://hackage.haskell.org/package/relation has this data type, but does not have composition?) bike-shedding the name and type: * composition vs. compose: the library usually favours the noun: intersection (not intersect), difference (not subtract) * order of arguments: mathematically speaking, it is of course very wrong, but it's consistent with the wrongness of (.) ... - J.W.