méthode de "jointure complète" pour les listes

Question

Disons que nous avons deux listes Seq[A] et Seq[B] de certains objets et que nous voulons les joindre sous certaines conditions (A, B) => Boolean. Cela pourrait être comme pour un élément de la première liste il y a plusieurs éléments correspondants du second. Si nous parlons de full join, nous voulons aussi savoir pour quels éléments pour les deux listes il n'y a pas de paire correspondante.

Ainsi, la signature serait:

def fullJoin[A, B](left: Seq[A], right: Seq[B], joinCondition: (A, B) => Boolean): (Seq[A], Seq[B], Seq[(A, B)]) 

Ou si nous profitions de chats Type de Ior:

def fullJoin[A, B](left: Seq[A], right: Seq[B], joinCondition: (A, B) => Boolean): Seq[Ior[A, B]] 

L'exemple:

scala> fullJoin[Int, Int](List(1,2), List(3,4,4), {_ * 2 == _ }) 
res4: (Seq[Int], Seq[Int], Seq[(Int, Int)]) = (List(1),List(3),List((2,4), (2,4))) 

L'idée est exactement la Identique à l'idée de joindre des tables en SQL.

La question est de savoir s'il existe des méthodes utilitaires similaires dans la bibliothèque standard. Si ce n'est pas le cas, discutons d'une solution élégante - dans un premier temps, avec des performances qui ne posent pas de problème (une complexité quadratique est bonne, comme pour Nested Loop).

Answer 1

Je pensais que le problème de jointure complète pouvait être résolu en termes de jointure à gauche. Pas vraiment optimisé, mais voici ma solution:

def fullJoin[A, B](left: Seq[A], right: Seq[B], joinCondition: (A, B) => Boolean): (Seq[A], Seq[B], Seq[(A, B)]) = { 
    val (notJoinedLeft, joined) = leftJoin(left, right, joinCondition) 
    val (notJoinedRight, _)  = leftJoin(right, left, (b: B, a: A) => joinCondition(a, b)) 
    (notJoinedLeft, notJoinedRight, joined) 
    } 

    def leftJoin[A, B](left: Seq[A], right: Seq[B], joinCondition: (A, B) => Boolean): (Seq[A], Seq[(A, B)]) = { 
    val matchingResult: Seq[Either[A, Seq[(A, B)]]] = for { 
     a <- left 
    } yield { 
     right.filter(joinCondition.curried(a)) match { 
     case Seq()    => Left(a) 
     case matchedBs: Seq[B] => Right(matchedBs.map((a, _))) 
     } 
    } 
    val (notMatched: Seq[A], matched: Seq[Seq[(A, B)]]) = partition(matchingResult) 
    (notMatched, matched.flatten) 
    } 

    def partition[A, B](list: Seq[Either[A, B]]): (Seq[A], Seq[B]) = { 
    val (lefts, rights) = list.partition(_.isLeft) 
    (lefts.map(_.left.get), rights.map(_.right.get)) 
    } 

Answer 2

Voici une solution qui tire parti des fonctionnalités intégrées bibliothèque scala être un peu plus concis:

def fullJoin[A, B](left: Seq[A], right: Seq[B], joinCondition: (A, B) => Boolean): (Seq[A], Seq[B], Seq[(A, B)]) = { 
    val matched = for (a <- left; b <- right if joinCondition(a, b)) yield (a, b) 
    val matchedLeft = matched.map(_._1).toSet 
    val matchedRight = matched.map(_._2).toSet 
    (left.filterNot(matchedLeft.contains), right.filterNot(matchedRight.contains), matched) 
}