Proposal: composition util for Maps

[Johannes Waldmann]

+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.