Proposal: composition util for Maps

[David Feuer]

For what it's worth, I'm fairly confident that implementation is optimal,
though I don't know how to even try to prove it. The only situation I see
where we could obviously do better is when ab maps many keys to the same
value and bc is very large compared to ab. In that case, it would make
sense to store a "cache" of lookups into bc. But the constant factors for
such an arrangement would be terrible, and there would be no benefit
whatsoever in the general case. So I think the simple thing is the right
thing here. As for names, I like compose. I support the proposal for the
reason Alexandre gives: it feels like a fundamental operation.

On Sun, Jul 7, 2019, 1:22 PM Alexandre Esteves <
alexandre.fmp.esteves at gmail.com> wrote:

> In https://github.com/haskell/containers/issues/647 I proposed the
> following util:
>
> 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. It's not particularly hard to
> write, but it does feel like a primitive-ish operation, and it's not
> obvious to me whether there's a faster implementation.
>
> Other name suggestions
> - (.)
> - chain
> - compose
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20190707/87fc1448/attachment.html>