Map functional combinators about collection-strawman HOT 8 CLOSED

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 a zip 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 and zipWithIndex. zip is currently present in those collections mixing IterablePolyTransforms. However, zipByKey* and mergeBy* 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 two Map'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 Maps 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 Nonedoes, 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.