Montag, 11. Dezember 2017

Unendliche Streams in Java 8 und 9

Mit Lambdas und Streams können wir seit Java 8 endlich etwas funktionaler programmieren. Ein wichtiges Konzept in funktionalen Sprachen sind unendliche Streams, die durch geeignete Bedingungen passend "abgebrochen" werden (die Streams sind natürlich nicht wirklich unendlich, sondern sie werden "lazy" - also erst bei Bedarf - ausgewertet). So etwas gibt es auch in Java, und das möchte ich mit dem folgenden Beispiel zeigen.

Es geht um den Luhn-Algorithmus zur einfachen Berechnung einer Prüfsumme. Inspiriert dazu wurde ich durch den JVM Functional Language Battle von Falk Sippach. Zu sehen gab es in dem Vortrag verschiedene Implementierungen, von klassischem, imperativem Java bis hin zu Scala, Frege und Java mit Vavr (vormals Javaslang).

Eine kurze Zusammenfassung vom Luhn-Algorithmus:
  • Gegeben sei eine nicht negative, ganze Zahl beliebiger Länge.
  • Von rechts nach links wird jede 2. Ziffer der Zahl verdoppelt. Entsteht dabei eine zweistellige Zahl, wird die Quersumme gebildet.
  • Alle so entstandenen Ziffern (einfach und verdoppelt) werden aufsummiert.
  • Die Prüfsumme ist gültig, wenn die Gesamtsumme ohne Rest durch 10 teilbar ist.
Wie kann man das mit Java-8-Streams implementieren? Dazu noch ohne Variablen, Zustandsänderungen und Fallunterscheidung? Beispielsweise so:

import java.util.PrimitiveIterator;
import java.util.stream.IntStream;

public class Luhn {

  public static boolean isValid(String number) {

    PrimitiveIterator.OfInt faktor =
      IntStream.iterate(1, i -> 3 - i).iterator();

    int summe = new StringBuilder(number).reverse()
      .toString().chars()
      .map(c -> c - '0')
      .map(i -> i * faktor.nextInt())
      .reduce(0, (a, b) -> a + b / 10 + b % 10);

    return (summe % 10) == 0;
  }
}

Als Beispiel durchlaufen wir isValid() mit dem String "8763".

Mit IntStream.iterate() erzeugen wir uns einen endlosen (aber lazy berechneten) Stream der Zahlen 1,2,1,2,1,2, ... – das ist der Faktor, mit dem jede Ziffer multipliziert wird.

Dann packen wir den Zahlen-String in einen StringBuilder, weil der eine reverse()-Methode bietet. Damit können wir die einzelnen Ziffern als chars()-Stream vorwärts durchlaufen (und müssen nicht von hinten zählen):

'3', '6', '7', '8'

Jedes Ziffern-char wir nun mit dem ersten map() auf den Ziffern-Wert 0..9 abgebildet und mit dem zweiten map() mit dem nächsten Faktor aus dem endlosen IntStream multipliziert:

3, 12, 7, 16

Mit reduce() berechnen wir nun die Quersumme aller dieser Zahlen, wobei wir für jede Zahl die Zehnerstelle (div 10) und die Einerstelle (mod 10) addieren, also

(0 + 3) + (1 + 2) + (0 + 7) + (1 + 6)

Ergibt 20, und das ist ohne Rest durch 10 teilbar. Somit ist die Prüfsumme gültig.


Mit Java 9 können wir uns das Umwandeln in einen String (und das Umkehren der Zeichenfolge) sparen, indem wir aus der zu prüfenden Zahl einen weiteren unendlichen Stream machen, den wir mit takeWhile() und einem geeigneten Lambda-Prädikat kappen:

import java.util.PrimitiveIterator;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

public class Luhn9 {

  public static boolean isValid(long number) {

    PrimitiveIterator.OfInt faktor =
      IntStream.iterate(1, i -> 3 - i).iterator();

    long summe = LongStream.iterate(number, n -> n / 10)
      .takeWhile(n -> n > 0)
      .map(n -> n % 10)
      .map(i -> i * faktor.nextInt())
      .reduce(0, (a, b) -> a + b / 10 + b % 10);

    return (summe % 10) == 0;
  }
} 

Der chars()-Stream in der Java-8-Lösung war nach der Verarbeitung aller Zeichen zu Ende. LongStream.iterate() in dieser Java-9-Variante teilt die zu prüfende Zahl dagegen endlos immer weiter durch 10, also z.B.

8763, 876, 87, 8, 0, 0, 0, ...

Wir müssen den Stream also nur verarbeiten, solange die Zahl größer Null ist. takeWhile() macht genau das und liefert folgenden endlichen Stream:

8763, 876, 87, 8

Das erste map() liefert einen Stream der letzten Ziffern (mod 10):

3, 6, 7, 8

Der Rest (Multiplizieren mit dem Faktor und Quersummen-Addition) ist dann wieder wie bei der Java-8-Lösung.

Das ist vielleicht noch nicht perfekt funktional, weil wir keine Funktionskomposition beliebiger passender Funktionen durchführen können, sondern auf die vorhandene Stream-API angewiesen sind. Aber für Java-Bordmittel ist das doch gar nicht so schlecht.


Und wer noch nicht genug davon hat: Ein anderes schönes Beispiel für unendliche Java-Streams ist die Berechnung von Kaprekar-Zahlen, was kürzlich als Challenge auf dev.to lief. Neben takeWhile() kommt bei der Java-Lösung noch limit() zum Einsatz, um einen unendlichen Stream nicht mit einer Bedingung, sondern mit einer festen Anzahl zu begrenzen.