Proposal: composition util for Maps

[Alexandre Rodrigues]

I can recall having had a need for this function a few times, so that’s cause for a +1 from me.
“compose” is not a bad name.

________________________________
From: Libraries <libraries-bounces at haskell.org> on behalf of Elliot Cameron <eacameron at gmail.com>
Sent: Sunday, July 7, 2019 8:28:31 PM
To: Tom Murphy
Cc: Haskell Libraries
Subject: Re: Proposal: composition util for Maps

+1 for "compose" and inclusion

On Sun, Jul 7, 2019, 2:17 PM <amindfv at gmail.com<mailto:amindfv at gmail.com>> wrote:
+1 from me on the addition and the name "compose"

Tom

El 7 jul 2019, a las 13:49, David Feuer <david.feuer at gmail.com<mailto:david.feuer at gmail.com>> escribió:

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<mailto: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<mailto:Libraries at haskell.org>
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
Libraries at haskell.org<mailto:Libraries at haskell.org>
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
Libraries at haskell.org<mailto: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/61256453/attachment.html>