Kolumne

Aus der Java-Trickkiste: Listen ohne Seiteneffekte

Arno Haase
java-trickkiste

© Software & Support Media

In der letzten Folge von „Aus der Java-Trickkiste“ haben wir seiteneffektfreies Programmieren betrachtet, was in Java im Wesentlichen Klassen bedeutet, bei denen alle Attribute final sind. Das hat den Vorteil, dass man Objekte herumreichen kann, ohne sich Gedanken machen zu müssen, wer sie verändern könnte – kurzum, es hilft dabei, robusten Code zu schreiben.

Wenn man ein Objekt „verändert“, erzeugt man eine Kopie mit dem veränderten Inhalt (Listing 1). Eine Bestellposition hat final-Felder für den Artikel und die bestellte Anzahl an Exemplaren des Artikels. Beide werden beim Erzeugen initialisiert.

Zum nachträglichen Ändern der bestellten Anzahl gibt es eine Methode mitAnzahl(). Die erzeugt ein neues BestellPos-Objekt mit geänderter Anzahl, während das Original unverändert bleibt.

public class BestellPos {
  private final String artikel;
  private final int anzahl;

  public BestellPos (String artikel, int anzahl) {
    this.artikel = artikel;
    this.anzahl = anzahl;
  }

  public BestellPos mitAnzahl (int neueAnzahl) {
    return new BestellPos (artikel, neueAnzahl);
  }

  public String getArtikel () { return artikel; }
  public int getAnzahl () { return anzahl; }
}

Unveränderliche Collections …

Man kann auch eine ganze Bestellung mit einer Liste von Positionen in einer unveränderlichen Datenstruktur ablegen (Listing 2). Dabei landen die Positionen in einem AHashSet – das ist eine unveränderliche Setimplementierung aus der Open-Source-Bibliothek a-foundation, die u. a. die wichtigsten Scala-Collection-Klassen nach Java portiert. Das Interface ASet kapselt dabei die konkrete Klasse.

public class Bestellung {
  private final String bestellNr;
  private final ASet positionen;

  public Bestellung (String bestellNr, Iterable positionen) {
    this.bestellNr = bestellNr;
    this.positionen = AHashSet.create (positionen);
  }

  public String getBestellNr () {
    return bestellNr;
  }

  public ASet getPositionen () {
    return positionen;
  }

  public String asString() {
    return "Bestellung " + bestellNr + ":\n" +
      positionen
        .map (b -> b.getAnzahl () + "x " + b.getArtikel ())
        .mkString("\n");
  }

  public int getGesamtAnzahl() {
    return positionen.foldLeft (0, (r, b) -> r + b.getAnzahl ());
  }

  public Bestellung mitNeuerAnzahl (BestellPos pos, int neueAnzahl) {
    return new Bestellung (bestellNr,
      positionen.map (b -> b != pos ? b : b.mitAnzahl (neueAnzahl)));
  }
    
  public Bestellung addPos (BestellPos pos) {
    ASet neueListe = positionen.added (pos);
    return new Bestellung (bestellNr, neueListe);
  } 

  public Bestellung removePos (BestellPos pos) {
    ASet neueListe = positionen.removed (pos);
    return new Bestellung (bestellNr, neueListe);
  }
}

Der Konstruktor initialisiert die Liste aus einem beliebigen Iterable mit Bestellpositionen – man kann also z. B. eine beliebige Collection hineinreichen, die dann aber mit AHashSet.create(…) in ein AHashSet kopiert wird.

Die Methode asString() erzeugt eine textuelle Beschreibung der Bestellung, die für jede Position eine Zeile mit Anzahl und Artikelnummer enthält. Das tut sie auf typisch funktionale Art durch Operationen auf der Liste, also ohne Schleife und veränderliche Zwischenobjekte.

In einem ersten Schritt erzeugt sie eine Liste mit den Beschreibungen der Positionen. Dazu ruft sie die Methode map() auf der Liste der Positionen auf. Die erhält eine Funktion als Parameter – hier als Lambda, mit Java 7 wäre es eine anonyme lokale Klasse – wendet sie auf jedes Element an und liefert eine Liste mit den Ergebnissen. In einem zweiten Schritt ruft sie auf dieser Liste mkString() auf, das ihre Elemente zu einem String zusammenfügt – hier mit einem Zeilenumbruch als Trennzeichen.

Die Methode getGesamtAnzahl() addiert die bestellte Anzahl über alle Positionen. Dazu benutzt sie die Methode foldLeft(), die die Elemente einer Liste schrittweise aggregiert. Sie erhält als Parameter einen Startwert – hier 0 – und eine Funktion, die aus dem alten Zwischenergebnis („r“) und einem Element („b“) ein neues Zwischenergebnis erzeugt, das dieses Element berücksichtigt. Oder konkret: Die Funktion addiert die bestellte Anzahl zum Zwischenergebnis und liefert diese Summe.

… und doch veränderlich

Die Methode mitNeuerAnzahl() „verändert“ schließlich die Liste, indem sie für eine Position eine neue Anzahl „setzt“. Tatsächlich verändert sie dabei keine bestehenden Objekte – die sind ja unveränderlich – sondern erzeugt Kopien mit neuen Werten, wo dies nötig ist.

Sie ruft dazu wieder ASet.map() auf und macht in der Transformationsfunktion eine Fallunterscheidung: Die zu modifizierende BestellPos wird durch eine Kopie ersetzt, alle anderen werden unverändert übernommen. Und mit dieser neuen Liste mit Positionen erzeugt sie ein Bestellung-Objekt, das sie dann auch zurückliefert – komplett ohne die ursprüngliche Bestellung verändert zu haben.

Diese Art des Umgangs mit Collections, indem man Funktionen auf ihnen operieren lässt, ist oft besser lesbar als explizite Schleifen. Das Stream API von Java 8 bietet ähnliche Funktionalität für normale Java Collections, und bis hierher hätten wir statt eines ASet auch z. B. eine mittels Collections.unmodifiableList() eingepackte ArrayList oder eine der Collection-Klassen aus Guava verwenden können (wenn auch mit etwas umständlicheren Aufrufen).

Ein ASet erlaubt es aber, einzelne Elemente „hinzuzufügen“ bzw. zu „entfernen“. Dazu gibt es die Methoden added() und removed(), die eine Kopie des ASet erzeugen, die ein zusätzliches Element enthält bzw. die ein Element nicht mehr enthält. Dabei wird typischerweise nur ein kleiner Teil der Daten tatsächlich kopiert, während ein großer Teil unverändert weiterverwendet wird, das Ganze ist also weniger ineffizient als es auf den ersten Blick wirkt. Solche Collections haben den etwas unglücklichen Namen „persistente“ Collections.

Die Methoden addPos() und removePos() in Listing 2 erzeugen mit diesen Methoden eine veränderte Liste mit Bestellpositionen, die sie dann in ein neues Bestellung-Objekt verpacken.

Anders als bei den Methoden add() und remove() bei normalen JDK Collections muss sich der Code dabei das veränderte ASet merken, das der Aufruf von added() und removed() zurückliefert. Deshalb implementieren die Collection-Klassen aus A-Foundation auch nicht die bekannten Interfaces java.util.Collection, List und Set: Alle Methoden, die Elemente hinzufügen oder entfernen, müssen bei unveränderlichen Collection-Klassen die neue Collection zurück liefern.

Der Vorteil dieser komplett unveränderlichen Datenstrukturen ist, dass man sie bedenkenlos herumreichen kann – fremder Code kann keine unerwarteten Veränderungen vornehmen. Der Code ist auch automatisch threadsicher: Weil alle Attribute final sind, können beliebige Threads gleichzeitig auf die Daten zugreifen, ohne dass man sich um Sichtbarkeit oder Konsistenz Gedanken machen muss.

Verkettete Listen

Eine weitere Datenstruktur, die in der funktionalen Programmierung weit verbreitet ist, ist die einfach verkettete Liste. Eine solche Liste hat eine Referenz auf ihr erstes Element und eine zweite Referenz auf den Rest der Liste; das erste Element wird oft als Head bezeichnet, der Rest der Liste als Tail. Beide Referenzen sind natürlich final, eine verkettete Liste ist also unveränderlich.

Das letzte Segment einer solchen Liste verweist als Tail auf die leere Liste. Die hat eine besondere Rolle, weil sie als einzige weder Head noch Tail hat, und sie wird häufig als nil bezeichnet.

Wenn man ein neues Element am Anfang zu einer Liste hinzufügt, kann man die alte Liste unverändert weiterverwenden, es kommt nur ein weiterer Knoten hinzu. Deshalb baut man Listen oft „von hinten nach vorne“ auf – man beginnt mit der leeren Liste, stellt das letzte Element voran etc. Diese Art, Elemente zu einer Liste hinzuzufügen, wird oft als cons bezeichnet.

Listing 3 erzeugt auf diese Weise eine Liste mit den beiden Elementen „x“ und „y“. Es beginnt mit AList.nil() – AList ist die verkettete Liste aus A-Foundation – und fügt zunächst „y“ und dann „x“ hinzu.

Diese Liste dient dann als Ausgangspunkt für zwei weitere Listen: Einmal wird „a“ vorangestellt, einmal „b“. Diese beiden Listen unterscheiden sich nur in ihrem ersten Segment, für den Rest der Liste teilen sie sich dieselbe Teilliste. Das geht nur deshalb, weil die Liste unveränderlich ist: Es kann nicht passieren, dass eine der Listen Daten verändert, auf die die andere sich verlässt. Abbildung 1 zeigt die Datenstrukturen aus Listing 3.

Abb.1: Mehrere Listen können sich denselben Tail teilen

Abb.1: Mehrere Listen können sich denselben Tail teilen

AList xy = AList.nil ()
  .cons ("y")
  .cons ("x");
AList axy = xy.cons ("a");
AList bxy = xy.cons ("b");

System.out.println (axy); // [a, x, y]
System.out.println (bxy); // [b, x, y]

assert axy.tail () == bxy.tail ();

Dieses Teilen von Teillisten kann man sich gezielt zunutze machen. Nehmen wir z. B. an, wir bauen ein soziales Netzwerk. Dort gibt es Personen mit „Freunden“. Und jede Person hat ein Set mit Freundesfreunden, um zum Beispiel Vorschläge für neue Kontakte zu machen (Listing 4).

Dabei ist nicht nur interessant, wer ein Freundesfreund von wem ist, sondern auch die Information, wer diese gemeinsamen Freunde sind. Deshalb ist eine Freundesfreundbeziehung als AList mit allen Schritten abgebildet.

public class Person {
  final String identifier;
  final ASet<AList> friendsOfFriends;

  ...

  ASet<AList> newFriendsOfFriends (Person newContact) {
    // TODO: Behandlung von Zyklen Dubletten etc.
    return newContact.friendsOfFriends
          .filter (l -> l.size () <= 3)           .map (l -> l.cons (newContact.identifier));
  }
}

Wenn Person A einen neuen „Freund“ B bekommt, werden dessen Freundesfreunde auch zu Freundesfreunden von A, allerdings mit einem zusätzlichen Schritt von A zu B. Die Methode newFriendsOfFriends() ermittelt diese zusätzlichen Beziehungsketten. Dazu betrachtet sie nur solche Freundesfreunde von B, die höchstens drei Schritte entfernt sind – ohne diesen Filter würden im Laufe der Zeit immer längere Ketten entstehen, und außerdem interessieren sich Nutzer im Allgemeinen nur für halbwegs nahe Beziehungen.

Fazit

Man kann auch in Java mit größeren unveränderlichen Datenstrukturen programmieren, und „persistente“ Collection-Klassen helfen dabei. Ein seiteneffektfreier Programmierstil hilft dabei, robusten Code zu schreiben, weil man jedes Stück Code isoliert verstehen kann – andere Teile eines Systems können nie interne Datenstrukturen in überraschender Weise verändern.

Außerdem erlauben unveränderliche Datenstrukturen andere Algorithmen, weil verschiedene Programmteile sich Daten teilen können. Das kann zu besser lesbarem Code führen, weil es weniger explizite Kopieroperationen gibt. Außerdem kann es Programme erheblich effizienter machen.

All das ist sicher kein Allheilmittel, aber es ist ein nützliches Paradigma, das in der Java-Welt stark unterrepräsentiert ist. Ich hoffe, dieser Artikel hat die Neugier geweckt.

Geschrieben von
Arno Haase
Arno Haase
Arno Haase ist freiberuflicher Softwareentwickler. Er programmiert Java aus Leidenschaft, arbeitet aber auch als Architekt, Coach und Berater. Seine Schwerpunkte sind modellgetriebene Softwareentwicklung, Persistenzlösungen mit oder ohne relationaler Datenbank und nebenläufige und verteilte Systeme. Arno spricht regelmäßig auf Konferenzen und ist Autor von Fachartikeln und Büchern. Er lebt mit seiner Frau und seinen drei Kindern in Braunschweig.
Kommentare

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu: