Map functional combinators

[pfcoperez]

Last year I opened a PR to Scala 2.12 aimed to include a join like operation subset within Map operations set:

scala/scala#5353

After some discussion it was clear that a more functional interface would fit better with the current map collections interface as join methods belong to the foreign (and not so abstract) realm of databases operations.

That was thoroughly syntetized by @szeiger 's comment, who proposed the following operation set:

def zipByKeyWith[W, X](that: Map[K, W])(f: (V, W) => X): Map[K, X]
def zipByKey[W](that: Map[K, W]): Map[K, (V, W)] = zipByKeyWith(that)(_ -> _)

And, to be able to handle non matching - in both maps - keys:

def mergeByKeyWith[W, X](that: Map[K, W](f: PartialFunction[(Option[V], Option[W]), X]: Map[K, X]
def mergeByKey[W](that: Map[K, W]): Map[K, (Option[V], Option[W])] = mergeByKeyWith(that)(PartialFunction(identity))

merge* would then be the way to provide left/right/full-outer join logical operations.

How could join operations be expressed using this API?

(NOTE: This is an application example, not part of the requested functionality)

• Inner join:

def join[K, VA, VB](a: Map[K, VA], b: Map[K, VB]): Map[K, (VA, VB)] =
    a zipByKey b

• 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 (Some(va), optVb) => va -> optVb }

• Right outer join:

def rightOuterJoin[K, VA, VB](a: Map[K, VA], b: Map[K, VB]): Map[K, (Option[VA], VB)] = 
    a.mergeByKeyWith(b) { case (optVa, Some(vb)) => optVa -> vb }

• Full outer join:

def fullOuterJoin[K, VA, VB](a: Map[K, VA], b: Map[K, VB]): Map[K, (Option[VA], Option[VB])] = 
    a.mergeByKey(b)

I think mergeByKey* operations are important as they cover all outer cases. In fact, zipByKeyWith implementation could be:

def zipByKeyWith[W, X](that: Map[K, W])(f: (V, W) => X): Map[K, X] = 
    mergeByKeyWith(that) { case (Some(va), Some(vb)) => f(va, vb) }

But I wouldn't use that implementation since, provided you're zipping only matching keys, you could avoid scrutinising that key set.

[julienrf]

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.

[Ichoran]

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

[pfcoperez]

@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?

[pfcoperez]

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

[LPTK]

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

[pfcoperez]

@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?

[DavidGregory084]

@pfcoperez Both cats and scalaz have an EitherOrBoth of some kind (Ior and \&/) so it's reasonable to assume that people find them useful

[pfcoperez]

@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) }