Relate the keys of one map to the values of the other, by using the
values of the former as keys for lookups in the latter.
Complexity: <math>, where <math> is the size of the first
argument
compose (fromList [('a', "A"), ('b', "B")]) (fromList [(1,'a'),(2,'b'),(3,'z')]) = fromList [(1,"A"),(2,"B")]
(compose bc ab !?) = (bc !?) <=< (ab !?)
Note: Prior to v0.6.4,
Data.Map.Strict exposed a version
of
compose that forced the values of the output
Map.
This version does not force these values.
Note on complexity
This function is asymptotically optimal. Given
n :: Map a b, m ::
Map b c, the composition essentially maps each
a in
n to
Maybe c, since the composed lookup yields
either one of the
c in
m or
Nothing. The
number of possible such mappings is <math>. We now follow a
similar reasoning to the one for
sorting. To distinguish
between <math> possible values, we need <math> bits. Thus,
we have a lower bound of <math> bits.
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.