"full join" -Methode für Listen

Question

Lets sagen wir haben eine zwei Listen und Seq[B] von bestimmten Objekten und wollen sie unter einer bestimmten Bedingung (A, B) => Boolean beitreten. Es könnte sein, dass für ein Element aus der ersten Liste mehrere übereinstimmende Elemente aus der zweiten Liste vorhanden sind. Wenn wir über full join sprechen, meinen wir, dass wir auch wissen wollen, für welche Elemente es in beiden Listen kein entsprechendes Paar gibt.

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

Oder wenn wir Ior Typ Vorteil Cats' nehmen:

So würde die Signatur sein

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

Das Beispiel:

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

Die Idee ist genau das Genau wie die Idee, Tabellen in SQL zu verbinden.

Die Frage ist, ob es ähnliche Utility-Methoden in der Standardbibliothek gibt. Wenn nicht, lassen Sie uns eine elegante Lösung diskutieren - zunächst, mit der Leistung kein Problem (eine quadratische Komplexität ist in Ordnung, wie für Nested Loop).

Answer 1

Ich dachte, das vollständige Join-Problem kann in Bezug auf Links Join gelöst werden. Nicht wirklich optimiert, aber hier ist meine Lösung:

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

Hier ist eine Lösung, die scala Bibliothek Funktionalität in-built Nutzt etwas prägnanter zu sein:

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