Proposal: composition util for Maps
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
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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
+1 from me on the addition and the name "compose" Tom
El 7 jul 2019, a las 13:49, David Feuer <david.feuer@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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
+1 for "compose" and inclusion On Sun, Jul 7, 2019, 2:17 PM <amindfv@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@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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
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@haskell.org> on behalf of Elliot Cameron <eacameron@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@gmail.com<mailto:amindfv@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@gmail.com<mailto:david.feuer@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@gmail.com<mailto:alexandre.fmp.esteves@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@haskell.org<mailto:Libraries@haskell.org> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list Libraries@haskell.org<mailto:Libraries@haskell.org> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list Libraries@haskell.org<mailto:Libraries@haskell.org> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
+1, and I like the name "compose". On Mon, 8 Jul 2019 at 06:42, Alexandre Rodrigues <alexandreR_B@outlook.com> wrote:
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@haskell.org> on behalf of Elliot Cameron <eacameron@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@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@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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
If someone wants to play around with the caching idea, this is (at least approximately) how I'd write it: data Res c a = Hit !(Maybe c) | Miss !(Maybe c) a deriving Functor compose bc ab = flip evalState Strict.empty $ traverseMaybeWithKey go ab where go _ b = do cache <- get case Strict.alterF (update b) b cache of Hit mc -> pure mc Miss mc cache' -> do put cache' pure mc update b Nothing = let mc = lookup b bc in Miss mc (Just mc) update _ (Just mc) = Hit mc On Sun, Jul 7, 2019, 1:49 PM David Feuer <david.feuer@gmail.com> wrote:
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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
participants (6)
-
Alexandre Esteves -
Alexandre Rodrigues -
amindfv＠gmail.com -
David Feuer -
Elliot Cameron -
George Wilson