Proposal: composition util for Maps

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Proposal: composition util for Maps

Alexandre Esteves
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: composition util for Maps

amindfv
+1 from me on the addition and the name "compose"

Tom

El 7 jul 2019, a las 13:49, David Feuer <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: composition util for Maps

Elliot Cameron-2
+1 for "compose" and inclusion

On Sun, Jul 7, 2019, 2:17 PM <[hidden email]> wrote:
+1 from me on the addition and the name "compose"

Tom

El 7 jul 2019, a las 13:49, David Feuer <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RE: 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 <[hidden email]> on behalf of Elliot Cameron <[hidden email]>
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 <[hidden email]> wrote:
+1 from me on the addition and the name "compose"

Tom

El 7 jul 2019, a las 13:49, David Feuer <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: composition util for Maps

George Wilson
+1, and I like the name "compose".

On Mon, 8 Jul 2019 at 06:42, Alexandre Rodrigues <[hidden email]> 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 <[hidden email]> on behalf of Elliot Cameron <[hidden email]>
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 <[hidden email]> wrote:
+1 from me on the addition and the name "compose"

Tom

El 7 jul 2019, a las 13:49, David Feuer <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: composition util for Maps

David Feuer
In reply to this post by David Feuer
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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: composition util for Maps

Johannes Waldmann-2
In reply to this post by Alexandre Esteves
+0.9

we can have it

> 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.

The given implementation traverses all of  ab
even if  bc  is empty. We could detect this.

But for  |bc| = 1, there is no work-around?

So,  O(|ab| * max(1, log |bc|)) ?


I think this could only be improved
if we had a representation of the inverse of  ab  as well.
I don't think it should be computed on-the-fly, as in
https://github.com/haskell/containers/issues/647#issuecomment-504798611
This would better be handled in a proper library for relations
( https://hackage.haskell.org/package/relation has this data type,
but does not have composition?)


bike-shedding the name and type:

* composition vs. compose: the library usually favours the noun:
  intersection (not intersect), difference (not subtract)

* order of arguments: mathematically speaking, it is of course
  very wrong, but it's consistent with the wrongness of (.) ...


- J.W.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: composition util for Maps

John Ericson-2
For what it's worth, I wish those were verbs too, so definitely +1
compose from me. (And +1 the idea too.)

John

On 7/8/19 7:18 AM, Johannes Waldmann wrote:

> bike-shedding the name and type:
>
> * composition vs. compose: the library usually favours the noun:
>    intersection (not intersect), difference (not subtract)
>
> * order of arguments: mathematically speaking, it is of course
>    very wrong, but it's consistent with the wrongness of (.) ...
>
>
> - J.W.
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: composition util for Maps

Tony Morris
+1 and compose

On Wed, Jul 24, 2019 at 8:07 AM John Ericson <[hidden email]> wrote:
For what it's worth, I wish those were verbs too, so definitely +1
compose from me. (And +1 the idea too.)

John

On 7/8/19 7:18 AM, Johannes Waldmann wrote:
> bike-shedding the name and type:
>
> * composition vs. compose: the library usually favours the noun:
>    intersection (not intersect), difference (not subtract)
>
> * order of arguments: mathematically speaking, it is of course
>    very wrong, but it's consistent with the wrongness of (.) ...
>
>
> - J.W.
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries