Erstellen einer unveränderlichen MultiMap in Scala

Dieser Beitrag zeigt ein paar nette Scala-Tricks, indem er eine unveränderliche MultiMap implementiert. Eine MultiMap ist eine besondere Art von Map: eine, die es erlaubt, jedem Schlüssel eine Sammlung von Elementen zuzuordnen, nicht nur einen einzelnen Wert. In diesem Beispiel verwenden wir zunächst Listen, um die Werte zu speichern, und erstellen so eine ListMultiMap

Hinzufügen von Elementen zu einer Map[A, List[B]]

Bevor wir irgendeinen Code schreiben, sollten wir uns fragen: Brauchen wir überhaupt eine ListMultiMap? Warum sollte eine normale Map[A, List[B]] nicht ausreichen?Natürlich kann eine Map[A, List[B]] unsere Daten gut aufnehmen, aber das Hinzufügen eines Wertes kann mühsam sein: Wenn der Schlüssel noch nicht existiert, muss eine neue Liste erstellt werden - andernfalls muss unser Wert zur bestehenden hinzugefügt werden. Fangen wir damit an, diesen Code in eine Hilfsfunktion zu packen: [code language="scala"] def addBinding[A,B](map: Map[A, List[B]], key: A, value: B): Map[A, List[B]] = map + (key -> { value :: map.getOrElse(key, Nil) }) [/code]

Typ-Aliase

Wenn Sie anfangen, das Muster Map[A, List[B]] häufig zu verwenden, können Sie die Dinge ein wenig einfacher machen, indem Sie einen Typ-Alias dafür definieren: [code language="scala"] type ListMultiMap[A,B] = Map[A,List[B]] def addBinding[A,B](map: ListMultiMap[A, B], key: A, value: B): ListMultiMap[A, B] = map + (key -> { value :: map.getOrElse(key, Nil) }) [/code] Ein Typ und sein Alias können ziemlich austauschbar verwendet werden, es gibt keine 'Hierarchie': Sie können eine ListMultiMap[A,B] verwenden, wo eine Map[A, List[B]] erwartet wird und umgekehrt.

Pimp My Library

Während diese Hilfsfunktion das Hinzufügen eines einzelnen Wertes zu einer MultiMap weniger mühsam macht, sieht sie bei mehreren Operationen nicht sehr hübsch aus: [code language="scala"] val original = Map(1 -> List(2, 3)) val intermediate = addBinding(original, 2, 5) val result = addBinding(step1, 2, 6) [/code] Um dies etwas einfacher zu gestalten, können wir das Muster pimp my library verwenden: [code language="scala"] implicit class ListMultiMap[A,B](map: Map[A, List[B]]) { def addBinding(key: A, value: B): ListMultiMap[A, B] = map + (key -> { value :: map.getOrElse(key, Nil) }) } val result = Map(1 -> List(2, 3)) .addBinding(2, 5) .addBinding(2, 6) [/code] Da hier die ListMultiMap[A,B] als implizite Klasse definiert ist, weiß der Scala-Compiler, wann immer Sie eine Map[A, List[B]] in Ihrem Code haben und versuchen, addBinding aufzurufen, wie die Konvertierung von Map[A, List[B]] zu ListMultiMap[A,B] durchzuführen ist.

Optimierung

Leider bedeutet dies, dass mit der Verwendung von addBinding ein Overhead verbunden ist: Jedes Mal, wenn es auf eine Map[A,List[B]] angewendet wird, wird ein neues ListMultiMap[A,B] Wrapper-Objekt erstellt. Glücklicherweise können wir diesen Overhead beseitigen, indem wir AnyVal erweitern und zu einer Value-Klasse machen: [code language="scala"] implicit class ListMultiMap[A,B](val map: Map[A, List[B]]) extends AnyVal { def addBinding(key: A, value: B): Map[A, List[B]] = map + (key -> { value :: map.getOrElse(key, Nil) }) } val result = Map(1 -> List(2, 3)) .addBinding(2, 5) .addBinding(2, 6) [/code] Dies teilt dem Compiler mit, dass die Klasse ListMultiMap keinen eigenen Zustand hat und er den Overhead der Erstellung eines Wrapper-Objekts optimieren kann.

Entfernen von Elementen

Natürlich ist eine Karte nicht vollständig ohne eine Möglichkeit, Bindungen zu entfernen: [code language="scala"] implicit class ListMultiMap[A,B](val map: Map[A, List[B]]) extends AnyVal { def addBinding(Schlüssel: A, Wert: B): Map[A, List[B]] = Karte + (Schlüssel -> { value :: map.getOrElse(key, Nil) }) def removeBinding(key: A, value: B): ListMultiMap[A, B] = map.get(key) match { Fall Keine => Karte case Some(Liste(value)) => Karte - Schlüssel case Some(Liste) => Karte + (Schlüssel -> list.diff(Liste(Wert))) } } [/code]

Kontrolle bei Bedarf

Ein weiterer Vorteil des "pimp my library"-Musters gegenüber der einfachen Vererbung von Map ist, dass der Benutzer durch die Wahl einer bestimmten Map-Implementierung die Kontrolle über die Leistungsmerkmale des Ergebnisses hat. Diese Kontrolle kann noch erweitert werden, indem der Benutzer auch seine List-Implementierung wählen kann. In der Tat können wir unsere MultiMap ganz einfach über jede unveränderliche Sequenz generisch machen: [code language="scala"] implicit class MultiMap[A,B](val map: Map[A, Seq[B]]) extends AnyVal { def addBinding(key: A, value: B, emptySeq: Seq[B] = Nil): Map[A, Seq[B]] = map + (key -> { value +: map.getOrElse(key, emptySeq) }) } [/code]

Generischer sein

Es gibt noch viele Möglichkeiten, diese Implementierung noch generischer zu gestalten, z.B. durch die Verwendung der Eigenschaft collection.MapLike und eine genauere Spezifikation der Varianz der generischen Typparameter. Dies sind jedoch Themen, die einen eigenen Blogpost verdienen.

Kurz gesagt

Mit Scala-Funktionen wie Typ-Aliasen und dem 'pimp my library'-Muster können Sie unterstützenden Code schreiben, der Ihre eigentliche Programmlogik von störendem Ballast befreit.