Comments (8)
Some random thoughts:
- Why restrict these operations to
Map
collections? - the name
zip
might be confusing because a “join” operation performs a cartesian product whereas we are used to have azip
operation that applies tupling element-wise.
from collection-strawman.
They work key-by-key. If you don't have maps, you don't have keys.
Also, because they work key-by-key, they are exactly analogous to a zip except instead of going by index, they go by key (which is the only sane thing to do anyway--zip on two sets makes very little sense).
from collection-strawman.
@julienrf following your questions order:
-
I took for granted that collections would include:
zip
,zipAll
andzipWithIndex
.zip
is currently present in those collections mixingIterablePolyTransforms
. However,zipByKey*
andmergeBy*
families should only be implemented by those collections where, no matter what type parametrization they may have, provide a key basis organization. -
My initial intention was to name these operations as
join
,leftOuterJoin
and so on. However, in the discussion I linked in the description of this issue, @Ichoran argued against those names and, after reading his reasoning, I can't help but concur. The point is twoMap
's inner join is equivalent to zipping the maps if their keys were considered "positions". A kind of not ordered zip, that is: A zip not given by each value position but by its key.
As an example: In relation to the access-element by index (From a logical standpoint, saving all other differences): Couldn't a Vector[T]
be regarded as a Map[Int, T]
? And, wouldn't, in that case, both "zip" families be equivalent?
from collection-strawman.
I was curious about how did they do this in Haskell, as a matter of fact, the Map
type has an operation merge: https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Map-Internal.html#v:merge
Quite similar to
def mergeByKeyWith[W, X](that: Map[K, W](f: PartialFunction[(Option[V], Option[W]), X]: Map[K, X]
With the main different that it encodes the behaviour to apply under the three matching possibilities with three separated functions:
- Key present in both maps:
SimpleWhenMatched k a b c
- Key present just in the left operand:
SimpleWhenMissing k a c
- Key present just in the right operand:
SimpleWhenMissing k b c
from collection-strawman.
the main different that it encodes the behaviour to apply under the three matching possibilities with three separated functions
That would probably be more efficient since it would avoid creating tuples and Some
wrappers. On the other hand having the PartialFunction
alternative seems better from a usability point of view in the context of Scala.
However, wouldn't it make more sense to introduce an EitherOrBoth
type instead of using a tuple of options? It would allocate less, and be more accurate as it cannot represent the impossible case of (None,None)
.
from collection-strawman.
@LPTK At the end of the day those Haskell's "tactics" wrap functions returning Maybe z
, that is Option[T]
. This way they decide whether or not include the key in the result.
Would EitherOrBoth
be part of the language or the collection API apart from Map
s API as Either
is? I like how it would look in this API but only if EitherOrBoth
was a general purpose construct.
I understand the raison d'etre of Either
as a way of including more information than Option
's None
does, but I don't know if there is such a reason for EitherOrBoth
beyond this context. Am I right?
from collection-strawman.
@pfcoperez Both cats and scalaz have an EitherOrBoth of some kind (Ior and \&/) so it's reasonable to assume that people find them useful
from collection-strawman.
@DavidGregory084 That's great! I didn't know it was a thing people used and if it was available it would be nice to apply @LPTK 's idea to have something like:
def mergeByKeyWith[W, X](that: Map[K, W](f: PartialFunction[EitherOrBoth[V,W], X]): Map[K, X]
I am also concerned about the discussed operation set performance:
On one hand, zipByKey*
could be implemented in a way that it would be only necessary to iterate over this
key set. e.g:
def zipByKeyWith[W, X](that: Map[K, W])(f: (V, W) => X): Map[K, X] =
for((k,va) <- this; vb <- that.get(k)) yield k -> f(va, vb)
On the other hand, mergeByKey*
should iterate over the union of both this
and that
key sets, always.
As described in the use case of the issue, you could implement left join using mergeByKeyWith
. In that case, even though, it might just need to visit all keys from this
, the program will visit all elements in this
and that
key sets just to discard all that
keys.
There are several approaches to avoid this but the idea of the three functions to encode the three behaviours could be rescued and expanded into: three partial functions:
def mergeByKeyWith[W, X](that: Map[K, W])(
justLeft: PartialFunction[V, X] = PartialFunction.empty)(
justRight: PartialFunction[W, X] = PartialFunction.empty)(
both: PartialFunction[(V, W), X] = PartialFunction.empty
): Map[K, X]
Given that the passed partial function might be PartialFunction.empty
, it is possible to know if a key set has to be iterated over or nor beforehand:
def mergeByKeyWith[W, X](that: Map[K, W])(
justLeft: PartialFunction[V, X] = PartialFunction.empty)(
justRight: PartialFunction[W, X] = PartialFunction.empty)(
both: PartialFunction[(V, W), X] = PartialFunction.empty
): Map[K, X] = { // Naive - and not compiled- implementation, just to illustrate
val masterKey = keys ++ {
if(justRight != PartialFunction.empty) that.keys
else Iterable.empty
}
for(k <- masterKey; ova <- get(k); ovb <- that.get(k)) yield {
...
...
...
}
}
Better performance left outer join:
def leftOuterJoin[K, VA, VB](a: Map[K, VA], b: Map[K, VB]): Map[K, (VA, Option[VB])] =
a.mergeByKeyWith(b) { case va => va -> None } () { case (va, vb) => va -> Some(vb) }
from collection-strawman.
Related Issues (20)
- TraversableOnce is missing
- Rename `to` to `as` HOT 10
- `seq` operation has been removed HOT 3
- Rewrite `--` operation to `&~` or `diff` HOT 1
- Rewrite `retain` to `filterInPlace`
- ArrayOps does not have a `view` operation anymore HOT 1
- Modularize the migration rewrite rules HOT 1
- Reorganize repositories
- Bring back Iterator.duplicate
- Set.apply / Map.apply don't use SetN / MapN
- We need dev-oriented documentation for M4 HOT 2
- ArrayOps doesn’t provide a sliding operation
- Make scala.Iterable[+A] = scala.collection.immutable.Iterable[A] HOT 8
- Setup collections-compat release infra
- add `()` to `toArray` HOT 1
- resolve status of `scala.collection.immutable.useBaseline` HOT 6
- IterableOnce.scala: def toSet[B >: A]: immutable.Set[B] should be def toSet: immutable.Set[A] HOT 2
- Main criticism HOT 3
- close or transfer all open issues and archive the repository HOT 1
- Delete and archive Gitter room HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from collection-strawman.