<div dir="auto">If someone wants to play around with the caching idea, this is (at least approximately) how I'd write it:<div dir="auto"><br></div><div dir="auto">data Res c a</div><div dir="auto">  = Hit !(Maybe c)</div><div dir="auto">  | Miss !(Maybe c) a</div><div dir="auto">  deriving Functor</div><div dir="auto"><br></div><div dir="auto">compose bc ab = flip evalState Strict.empty $ traverseMaybeWithKey go ab</div><div dir="auto">  where</div><div dir="auto">    go _ b = do</div><div dir="auto">      cache <- get</div><div dir="auto">      case Strict.alterF (update b) b cache of</div><div dir="auto">        Hit mc -> pure mc</div><div dir="auto">        Miss mc cache' -> do</div><div dir="auto">          put cache'</div><div dir="auto">          pure mc</div><div dir="auto">    update b Nothing =</div><div dir="auto">      let mc = lookup b bc</div><div dir="auto">      in Miss mc (Just mc)</div><div dir="auto">    update _ (Just mc) = Hit mc</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Jul 7, 2019, 1:49 PM David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div>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.<br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Jul 7, 2019, 1:22 PM Alexandre Esteves <<a href="mailto:alexandre.fmp.esteves@gmail.com" rel="noreferrer noreferrer" target="_blank">alexandre.fmp.esteves@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>In <a href="https://github.com/haskell/containers/issues/647" rel="noreferrer noreferrer noreferrer" target="_blank">https://github.com/haskell/containers/issues/647</a> I proposed the following util:<br></div><div><br></div><div>composition :: Ord b => Map b c -> Map a b -> Map a c<br>composition bc ab = flip mapMaybe ab $ flip lookup bc<br><br>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.</div><div><br></div><div>Other name suggestions</div><div>- (.)</div><div>- chain</div><div>- compose</div><div><br></div><div><br></div></div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div></div></div>
</blockquote></div>