19
Apr
14

zipWith in Java 8

Heute einmal ein ziemlich einfaches Beispiel, wie Lambdas das Leben in Java 8 leichter machen. In Haskell und Scala gibt es die Funktione zipWith, mit der zwei Datenstrukturen wie Listen durch elementweise Verknüfung zu einer neuen “zusammengeklebt” werden. Dabei muss man aufpassen: Ist eine der Ausgangsstrukturen länger als die andere, werden die “überflüssigen” Elemente einfach ignoriert. In Java bietet sich so eine Funktion an mindestens zwei Stellen an: Bei Iterables und bei den neuen Streams. Da ich mich mit letzteren (noch) nicht so gut auskenne, will ich heute den einfacheren ersten Fall behandeln.

Ein besonders nützlicher Anwendungsfall für zipWith ist, wenn man mit der erweiterten for-Schleife zwei Collections gleichzeitig durchgehen will – vorher musste man meist auf andere Sprachmittel (z.B. Indexe oder Iteratoren) ausweichen. Wie könnte nun so eine Schleife aussehen?

List<String> strings = Arrays.asList("a","b","c");
List<Integer> ints = Arrays.asList(6,9,14,32);
for(String result : zipWith(strings, ints, (s,i) -> s + i)) {
   System.out.println(result);
}

Das erwartete Ergebnis wären hier die Zeilen “a6″, “b9″ und “c14″. Natürlich wäre auch eine anonyme Klasse an Stelle des Lambda-Ausdrucks möglich gewesen, aber erst durch diesen wird das ganze Konstrukt lesbar. Die Umsetzung ist trivial:

import java.util.function.BiFunction;
...
public static <A,B,C> Iterable<C> zipWith(Iterable<A> iterableA, Iterable<B> iterableB, BiFunction<A,B,C> fn) {
    return () -> new Iterator<C>() {
        private Iterator<A> itA = iterableA.iterator();
        private Iterator<B> itB = iterableB.iterator();

        public boolean hasNext() {
            return itA.hasNext() && itB.hasNext();
        }

        public C next() {
            return fn.apply(itA.next(), itB.next());
        }
    };
}

Wer sich wundert, wo das “new Iterable” geblieben ist: Da das Interface nur eine Methode (nämlich iterator()) besitzt, können wir es durch einen Lambda-Ausdruck ersetzen. Wir brauchen auch die remove-Methode von Iterator nicht zu implementieren, es gibt in Java 8 eine Default-Methode dafür (die eine UnsupportedOperationException wirft). Und als letztes fällt auf, dass wir aus dem Lambda-Ausdruck heraus auf iterableA und iterableB zugreifen konnten, ohne dass wir diese final machen mussten. Da beide Argumente nicht (weder in der Methode noch im Lambda-Ausdruck) verändert werden, sind sie “effektiv final” und benötigen keinen entsprechenden Modifikator.

Das war jetzt etwas leichtere Kost, aber ich hoffe trotzdem ein wenig nützlich.

Wer weiß, wie man das Gleiche mit Streams anstellt, darf seine Lösung hier gerne vorstellen, ich bin gespannt darauf…

05
Apr
14

Java 8 und der Y-Kombinator

So schön Lambda-Ausdrücke auch sind, sie haben wenigstens eine Achillesferse: Rekursion. Betrachten wir folgendes Beispiel, das schon seit Java 5 funktionieren würde (ein entsprechendes Function-Interface einmal vorausgesetzt):

...
Function<Integer, Long> fac = new Function<Integer, Long>() {
    @Override
    public Long apply(Integer n) {
        return n == 0 ? 1L : n * apply(n-1);
    }
};

System.out.println(fac.apply(10)); //--> 3628800
...

So weit, so gut und auch so langweilig: Die gute alte Fakultät. Aber wie lässt sich die Definition der anonymen Klasse durch einen Lambda-Ausdruck ersetzen? Hier zwei Beispiele dafür, wie es schon einmal nicht geht:

//Compiler-Fehler: "Variable fac might not have been initialized"
Function<Integer, Long> fac = n -> n == 0 ? 1L : n * fac.apply(n-1);  

//this verweist hier auf die umgebende Klasse, nicht auf den Lambda-Ausdruck selbst
Function<Integer, Long> fac = n -> n == 0 ? 1L : n * this.apply(n-1);  

Wir müssen also tiefer in die Trickkiste greifen. Man bräuchte einen Weg, um die Rekursion sozusagen “explizit” zu machen. Erfreulicherweise ist dieses Problem schon lange gelöst und gehört zur Folklore der funktionalen Sprachen: Man verwendet einen Fixpunkt-Kombinator wie den Y-Kombinator. Ich will an dieser Stelle nicht genauer auf die Funktionsweise eingehen, hauptsächlich um zu verhindern, dass mein Gehirn schmilzt, aber auch, weil man unter Magiern keine Tricks verrät. Deshalb hier eine sehr direkte Umsetzung dieses Konzepts (z.B. ohne weitere Vorkehrungen, um einen Stacküberlauf zu verhindern):

...
public static <X,Y> Function<X,Y> yCombinator(Function<Function<X,Y>,Function<X,Y>> f) {
   return x -> f.apply(yCombinator(f)).apply(x);
}
...

Function<Integer,Long> fac = yCombinator(f -> n -> n == 0 ? 1L : n * f.apply(n-1));

System.out.println(fac.apply(10)); //--> 3628800

Wer mehr dazu erfahren will, sollte sich den Wikibook-Eintrag zu Haskell’s fix-Funktion anschauen. Aber selbst wenn man die “Magie” nicht im Detail nachvollziehen kann oder will, ist es nützlich zu wissen, dass es diesen Trick gibt. Es ist auch ein schönes Beispiel dafür, dass es sich lohnen kann, einmal über den objektorientierten Tellerrand zu schauen, um die tollen neuen Features von Java 8 auch wirklich ausnutzen zu können.

30
Mär
14

Kann Java abstrakte Typ-Member simulieren?

Scala kennt von Anfang an abstrakte Typ-Member als Alternative zu Generics. Eine Übersicht findet sich hier, und ich habe auch schon damit herumgespielt. Die Kurzfassung: Während generische Klassen ihre Parameter nach außen bekanntmachen, und diese überall mit “durchgeschleift” werden (müssen), werden abstrakte Typ-Member eher als eine Art Implementierungsdetail angesehen und somit sozusagen als “innere Angelegenheit” behandelt.

Und gestern abend dämmerte mir, das Java zumindest prinzipiell etwas Ähnliches erlaubt – und nicht erst seit Java 8. Ich habe keine Ahnung, wie weit diese “Technik” trägt – und ganz sicher ist sie nicht so flexibel wie Scalas Ansatz, der ja “dafür gebaut” worden ist. Aber ich werde gleich zwei Instanzen mit unterschiedlichen Member-Typen in ein und dieselbe Liste packen – ohne Wildcards, Raw-Types, Casts oder Compiler-Warnungen. Sozusagen “innen generisch, außen nicht” – ähnlich wie bei abstrakten Typ-Membern:

public class Outer<T> {

    public class Inner {
        public final T t;

        public Inner(T t) {
            this.t = t;
        }
    }

    public static void main(String[] args) {
        List<Outer.Inner> list = new ArrayList<>();
        list.add(new Outer<String>().new Inner("blubb"));
        list.add(new Outer<Integer>().new Inner(42));
        for(Outer.Inner inner : list) {
            System.out.println(inner.t);
        }
    }
}

Tadaaaaa! Das ist also der Trick: Innere Klassen, die die Generics von ihren äußeren Klassen “benutzen”. Übrigens: Wer solche seltsamen Konstruktoraufrufe wie im Beispielcode noch nicht gesehen hat, ist nicht allein – ich kannte die Syntax auch nicht, bis ich für die “Java Programmer”-Zertifizierung von Oracle lernen musste (daher auch die “Inspiration” für diesen etwas kranken Code). Ich muss erst einmal sehen, in wie weit dieses Konstrukt überhaupt sinnvoll ist, und wie groß die Beschränkung durch die erzwungene “Innerklassigkeit” in der Praxis ist. Falls ihr auch damit herumspielt, würden mich natürlich die Ergebnisse eurer Experimente brennend interessieren.

[Update]
Ich bin darauf hingeweisen worden, dass der “volle” Typ meiner Liste eigentlich etwas wie List<Outer<String>.Inner> sein müsste, ich hier also doch mit Raw-Types arbeite (auch wenn ich keine Warnung sehe). Das macht das Ganze natürlich hinsichtlich der Typsicherheit obsolet, weil damit kein Unterschied zu einer normalen generischen Top-Level-Klasse, die als Raw-Typ verwendet wird, besteht. Schade…

12
Feb
14

Continuations in Java 8

Mit Java 8 in den Startlöchern bietet sich an, mal zum Vergleich ältere Blog-Beiträge zu “lambdafizieren”. Hier ist der aktualisierte Code zu Continuations in Java, der deutlich die Mächtigkeit der Lambdas und Default-Methoden zeigt:

import java.util.function.Function;

public interface Cont<R,A> {

    R runCont(Function<A,R> fn);

    public default <B> Cont<R,B> bind(final Function<A,Cont<R,B>> f){
        return k -> Cont.this.runCont(a -> f.apply(a).runCont(k));
    }

    public static <R,T> Cont<R,T> Return(final T t) {
        return fn -> fn.apply(t);
    }
}

Und das Beispiel:

import java.util.function.BiFunction;

public class PythExample {

    public static <R> BiFunction<Integer, Integer, Cont<R, Integer>> pythCont() {
        return (x, y) -> Cont.<R, Integer>Return(x * x).bind(
                a -> Cont.<R, Integer>Return(y * y).bind(
                        b -> Cont.<R, Integer>Return(a + b)));
    }

    public static void main(String... args) {
        PythExample.<Void>pythCont().apply(3, 4).runCont(
                r -> { System.out.println(r);  return null; });
    }
}

Aus der abstrakten Klasse ist (dank Default-Methode) ein Interface geworden, um die Lambda-Syntax nutzen zu können. Auch das Anwendungsbeispiel wurde deutlich gestrafft. Wie man schön sehen kann, sind die einstigen Monstrositäten jetzt tatsächlich “benutzbar”, auch wenn man sich sicher erst an die Syntax gewöhnen muss.

10
Feb
14

Top Ten “Was man an Java verbessern könnte”

Kurz vor dem langersehnten Java 8-Release drängt sich mir die Frage auf, was mich an Java am meisten stört, oder anders gesagt, was man (auch mit den modernen Sprachmitteln) unbedingt besser machen sollte, wenn man nicht auf Kompatibilität achten müsste. Dabei will ich gar nicht von gravierenden Neuerungen reden, die den Charakter der Sprache komplett ändern würden, sondern von den kleinen, vermeidbaren Hässlichkeiten. Natürlich ist das ein ziemlich kontroverses Thema, und jeder wird da seine eigene Liste haben…

  1. Unnötige Schlüsselwörter vermeiden: volatile, transient und strictfp könnten Annotationen sein, instanceof könnte zu einer Methode von Object werden
  2. Arrays keine Extrawurst mehr braten: Ein Array könnte sich syntaktisch an den Collections orientieren (auch wenn es vom Compiler “hintenherum” anders behandelt wird) und müsste bei Zuweisungen invariant sein, um ArrayStoreExceptions zu vermeiden.
  3. Einen “Selbsttyp” einführen: So wie this für das aktuelle Objekt steht, müsste ein generischer Typ This für die aktuelle Klasse stehen. Damit sind Tricksereien wie z.B. in der Typsignatur der Enum-Klasse nicht mehr nötig. Elternklassen und Interfaces können so problemlos Methoden definieren, die die konkrete Klasse als Argument oder Rückgabewert besitzen.
  4. Primitive als generische Typen erlauben: Entsprechender Code kann automatisch generiert werden, ähnlich wie in Scala mit @specialized.
  5. Mehr Sicherheit gegen Nullpointer-Exceptions: Verbindliche, geprüfte Annotationen für Argumente, die null sein können.
  6. Object entrümpeln: Was soll die clone()-Methode in Object? Muss jedes Object als Lock dienen können, wozu soll man notify() und wait() mitschleppen? Wieso equals(), wenn nicht jede Klasse wirklich “vergleichbar” ist? Wieso hashCode(), wenn viele Klassen nicht als Schlüssel einer Map taugen? Weg damit, in eigene Interfaces.
  7. Vernüftiges Serializable: Ein bisschen mehr Unterstützung wäre nicht schlecht, etwa über Annotationen (z.B. um einen “Konverter” anzugeben, der eigentlich nicht-serialisierbare Member doch serialisieren kann).
  8. Unveränderliche Collections: Nein, nicht das, was Collections.unmodifiableList und so liefern, sondern immutable Collections, die ein neues Objekt liefern, wenn z.B. ein Element hinzugefügt oder gelöscht wird.
  9. String zu einem Iterable machen: Es ist völlig unverständlich, warum man nicht mit einer erweiterten For-Schleife über einen String iterieren kann.
  10. Vergleiche verbessern: Comparable streichen, Comparator.compare() ein Enum zurückgeben lassen, statt dafür int zu missbrauchen.

Wie sieht eure Liste aus?

01
Sep
12

Völlig entkoppelt – das Modell

Ich hatte mir schon länger vorgenommen, endlich wieder etwas über Scala zu schreiben. In dieser kleinen Serie möchte ich anhand eines kleinen Beispiels zeigen, wie weit man Entkopplung in Scala nur mit “Bordmitteln” treiben kann, und welche Techniken dabei helfen. Als Beispiel habe ich mir das altbekannte Spielchen “Sokoban” herausgepickt, und mich bei der Umsetzung grob an diesem Ruby Quiz orientiert, wo es auch eine Datei mit Leveln gibt.

Und schon stellt sich die erste Frage, nämlich womit man anfangen sollte. Ich denke, man sollte mit dem Modell beginnen, schon deshalb, weil dieses keine Abhängigkeiten zu den anderen Komponenten haben sollte. Fangen wir also damit an!

Zuerst einmal benötigen wir Bewegungsrichtungen und Positionen:

sealed abstract class Move(val dx: Int, val dy: Int)
case object North extends Move(0, -1)
case object South extends Move(0, 1)
case object West extends Move(-1, 0)
case object East extends Move(1, 0)

case class Pos(x: Int, y: Int) {
  def goto(m: Move) = Pos(x + m.dx, y + m.dy)
  def max(that:Pos) = Pos(math.max(this.x, that.x), math.max(this.y,that.y))
}

Sehr schön: Unsere Klassen sind nicht völlig dumm, sie können schon ein wenig rechnen. Die Positionsklasse kann eine Richtung dazuaddieren, und auch das Maximum bezüglich einer weiteren Position bestimmen (was praktisch ist, um die Größe des Levels sozusagen “ganz nebenbei” zu ermitteln).

Nun zum eigentlichen Level. Auch hier bietet sich eine Fall-Klasse an, allerdings tue ich etwas ungewöhnliches: Ich mache alle Argumente private. Der Grund dafür ist, dass die gewählten Argumenttypen wirklich nur ein Implementationsdetail sind. Ich hätte z.B. statt der Sets auch Listen nehmen können, oder das ganze Spielfeld als Array darstellen. Code von außen sollte daran nicht herumwursteln. Die Level-Klasse weiß am besten, wie sie Inkonsistenzen vermeidet oder wann der Zähler für die Züge hochgesetzt werden muss. Damit man trotzdem problemlos ein “leeres” Level erstellen kann, habe ich allen Argumenten Default-Werte mitgegeben.

case class Level(private val walls: Set[Pos] = Set.empty,
                 private val storages: Set[Pos] = Set.empty,
                 private val crates: Set[Pos] = Set.empty,
                 private val worker: Pos = Pos(-1, -1),
                 private val size: Pos = Pos(-1, -1),
                 private val moves: Int = 0) {

  def addWall(pos:Pos) = copy(walls = walls + pos, size = size max pos)
  def addStorage(pos:Pos) = copy(storages = storages + pos, size = size max pos)
  def addCrate(pos:Pos) = copy(crates = crates + pos, size = size max pos)
  def setWorker(pos:Pos) = copy(worker = pos)
  private def removeCrate(pos:Pos) = copy(crates = crates - pos)
  private def increaseMoves = copy(moves = moves + 1)

  private def isWall(pos: Pos) = walls.contains(pos)
  private def isStorage(pos: Pos) = storages.contains(pos)
  private def isCrate(pos: Pos) = crates.contains(pos)
  private def isWorker(pos: Pos) = pos == worker
  private def isFree(pos: Pos) = ! (isCrate(pos) || isWall(pos))

  def isSolved = storages == crates
  def getMoves = moves

  def move(m: Move) = {
    val newWorkerPos = worker.goto(m)
    val newCratePos = newWorkerPos.goto(m)
    if (isFree(newWorkerPos))
      Some(setWorker(newWorkerPos).increaseMoves)
    else if (isCrate(newWorkerPos) && isFree(newCratePos))
      Some(setWorker(newWorkerPos).removeCrate(newWorkerPos).addCrate(newCratePos).increaseMoves)
    else None
  }

  override def toString = {
    def toChar(pos: Pos) = (isStorage(pos), isCrate(pos), isWorker(pos), isWall(pos)) match {
      case (true,  true,  false, false) => '*' //crate on a storage position
      case (true,  false, true,  false) => '+' //worker on a storage position
      case (true,  false, false, false) => '.' //storage position
      case (false, true,  false, false) => 'o' //crate
      case (false, false, true,  false) => '@' //worker
      case (false, false, false, true)  => '#' //wall
      case (false, false, false, false) => ' ' //empty
      case _ => sys.error("Illegal level state for " + pos)
    }

    (for (y <- 0 to size.y) yield
      (for (x <- 0 to size.x; ch = toChar(Pos(x, y))) yield ch)
        .mkString + "\n")
      .mkString
  }
}

Wie für Fall-Klassen üblich ist Level unveränderlich, und um neue Versionen zu erstellen wird ausgiebig die copy-Methode benutzt. Ansonsten gibt es viele kleine Helfermethoden, die sowohl das Einlesen eines Levels unterstützen wie auch die move- und toChar-Methode vereinfachen. Leider ist die List-Comprehension am Ende von toString nicht sehr elegant, weil ich keinen cleveren Weg gefunden habe, die notwendingen Zeilenumbrüche einzuschmuggeln. Vielleicht hat ja jemand eine Idee dazu?

Die bei toChar verwendete Pattern-Matching-Technik kann helfen, längere if-else-Kaskaden zu vermeiden. Als Anfänger beschränkt man sich meist darauf, auf die Methoden-Argumente selbst zu matchen, aber in vielen Fällen kommt man durch Umstellungen, Kombinationen oder Vorberechnungen zu besseren Lösungen.

Die Kapselung der Level-Klasse ist nicht perfekt. Würde man z.B. das Companion-Objekt zum Einlesen verwenden, könnte man die ganzen add-Methoden “privatisieren”. Aber ich wollte auch hier flexibel bleiben: Das Model sollte sich möglichst nicht ändern, wenn man z.B. ein anderes Dateiformat verwendet. Hier der Lade-Mechanismus:

import io.Source

trait Loader {
    def getLevels(name: String) : List[Level]
}

trait TextFileLoader extends Loader {

  override def getLevels(name: String) = Source.fromFile("./" + name).
    getLines().foldRight(List(List[String]()))((e: String, s: List[List[String]]) =>
      if (e.trim.isEmpty) List[String]() :: s else (e :: s.head) :: s.tail).
    map(makeLevel(_))

  private def makeLevel(list: List[String]) = list.zipWithIndex.foldLeft(Level()) {
    (level, yPair) => yPair._1.zipWithIndex.foldLeft(level) {
        (level, xPair) =>
          val pos = Pos(xPair._2, yPair._2)
          xPair._1 match {
            case '.' => level.addStorage(pos)
            case '#' => level.addWall(pos)
            case 'o' => level.addCrate(pos)
            case '@' => level.setWorker(pos)
            case '+' => level.setWorker(pos).addStorage(pos)
            case '*' => level.addCrate(pos).addStorage(pos)
            case ' ' => level
            case ch => sys.error("Unknown character " + ch)
          }
      }
  }
}

Die getLevel-Methode sieht gefährlicher aus, als sie ist: Da die Levels nur durch Leerzeilen getrennt in der Datei gespeichert sind, muss man etwas Aufwand treiben, um sie auseinanderzudividieren. Die makeLevel-Methode ist auch nicht besonders schön. Das Problem dabei ist, dass wir nicht nur die Zeichen brauchen, sondern auch ihre Position. Vielleicht gibt es hier bessere Techniken als das doppelte zipWithIndex, und mit dem Falten habe ich es wahrscheinlich auch ein wenig übertrieben. Allerdings ist das Hinzufügen neuer Elemente zum Level recht transparent – besser jedenfalls, als wenn wir hier selbst mit den Sets herumhantieren würden.

So weit haben wir also ein Modell, das absolut nichts vom Rest der Welt weiß, und einen austauschbaren Lade-Mechanismus.

Nächstes Mal bringen wir das Spiel zum Laufen, allerdings erst einmal ganz bescheiden auf der Konsole.

30
Mär
12

Monoide in Java

Eine Abstraktion aus Haskell, die problemlos in Java abgebildet werden kann, sind Monoide. Keine Angst, die Idee dahinter ist so simpel, dass der bombastische Name schon fast ein wenig peinlich ist.

Zuerst einmal haben wir eine assoziative binäre Operation, die uns eine Halbgruppe beschert.

public interface Semigroup<T> {
    //a binary associative operation
    public T o(T t1, T t2);
}

Zu einem richtigen Monoid fehlt dann nur noch ein neutrales Element:

public interface Monoid<T> extends Semigroup<T> {
    //the neutral element regarding o
    public T empty(); 
}

Es gibt nützliche Klassen, die Halbgruppen, aber keine Monoide sind (ein Beispiel aus Haskell wäre der Typ “NonEmpty” für nicht-leere Listen), deshalb haben ich die zwei Interfaces nicht zusammengefasst.

Wenn wir diese Interfaces implementieren, sollten wir darauf achten, dass wir die Gesetze einhalten, nämlich die Assoziativität: o(x,o(y,z)) = o(o(x,y),z) und die “Neutralität” des neutralen Elements: o(empty,x) = o(x,empty) = x.

Welche Monoide fallen uns nun ein? Wie wäre es mit Zahlen und Booleans:

public enum IntMonoid implements Monoid<Integer> {
    Sum(){
        @Override
        public Integer empty() {
            return 0;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return t1 + t2;
        }
    },
    Product(){
        @Override
        public Integer empty() {
            return 1;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return t1 * t2;
        }
    },
    Min(){
        @Override
        public Integer empty() {
            return Integer.MAX_VALUE;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return Math.min(t1, t2);
        }
    },
    Max(){
        @Override
        public Integer empty() {
            return Integer.MIN_VALUE;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return Math.min(t1,t2);
        }
    }
}

public enum BoolMonoid implements Monoid<Boolean> {
    And(){
        @Override
        public Boolean empty() {
            return Boolean.TRUE;
        }

        @Override
        public Boolean o(Boolean t1, Boolean t2) {
            return t1 && t2;
        }
    },
    Or(){
        @Override
        public Boolean empty() {
            return Boolean.FALSE;
        }

        @Override
        public Boolean o(Boolean t1, Boolean t2) {
            return t1 || t2;
        }
    }
}

Oder auch Strings:

public enum StringMonoid implements Monoid<String> {
    Append(){
        @Override
        public String empty() {
            return "";
        }

        @Override
        public String o(String t1, String t2) {
            return t1 + t2;
        }
    }
}

Analoges könnte man für Listen oder Sets definieren. Nun fragt man sich sicher langsam, was man alles damit anstellen kann. Eine der Hauptanwendungen ist das “Falten”, also das Zusammenfassen aller Werte eines Container-Typs:

public enum Fold {
    ;

    public static <T> T fold(Semigroup<T> semigroup, T start, T... ts) {
        T result = start;
        for(T t : ts) {
            result = semigroup.o(result, t);
        }
        return result;
    }

    public static <T> T fold1(Monoid<T> monoid, T... ts) {
        return fold(monoid, monoid.empty(), ts);
    }

    public static <T> T fold(Semigroup<T> semigroup, T start, Iterable<T> ts) {
        T result = start;
        for(T t : ts) {
            result = semigroup.o(result, t);
        }
        return result;
    }

    public static <T> T fold1(Monoid<T> monoid, Iterable<T> ts) {
        return fold(monoid, monoid.empty(), ts);
    }
}

Das sieht dann so aus:

import static rummage.monoid.Fold.*;
import static rummage.monoid.StringMonoid.*;

System.out.println(fold1(Append,"Eins","Zwei","Drei","Vier"));
//EinsZweiDreiVier

Leider ist hier die Stringverkettung nicht so effizient wie mit einem StringBuilder, also sollte man aufpassen, dass man nicht zuviele Teilstrings auf diese Weise verkettet. Im “richtigen Leben” würde ich deshalb eine spezialisierte Methode für Append in Fold bereitstellen.

Man kann auch neue Monoide aus vorhandenen basteln:

public enum DualMonoid {
    ;
    public static <T> Monoid<T> dual(final Monoid<T> monoid) {
       return new Monoid<T>() {
           @Override
           public T empty() {
               return monoid.empty();
           }

           @Override
           public T o(T t1, T t2) {
               return monoid.o(t2,t1);
           }
       };
    }

    public static <T> Semigroup<T> dual(final Semigroup<T> semigroup) {
        return new Semigroup<T>() {
            @Override
            public T o(T t1, T t2) {
                return semigroup.o(t2,t1);
            }
        };
    }

}

Damit funktioniert dann folgender Trick:

import static rummage.monoid.Fold.*;
import static rummage.monoid.StringMonoid.*;
import static rummage.monoid.DualMonoid.*;
...
System.out.println(fold1(dual(Append),"Eins","Zwei","Drei","Vier"));
//VierDreiZweiEins

In Haskell hat man noch wesentlich mehr Monoide, z.B. für Funktionen (“Endo”) oder für algebraische Datentypen wie Maybe, Either und Tupel, und mehr Möglichkeiten, diese zu kombinieren. In Java sind die “bequemen” Anwendungsmöglichkeiten insbesondere durch fehlende Closures etwas eingeschränkt, weshalb auch unser Fold im Vergleich zu Haskells Typklasse “Foldable” bescheiden ausfällt.

Trotzdem finde ich es interessant, solche Abstraktionsmöglichkeiten einmal näher zu untersuchen, als immer die gleichen stupiden Schleifen zu schreiben. Und auch wenn die Schleifenlösung einfacher erscheint, gibt es Tücken: Wer noch nie bei der Minimumsuche den Startwert einmal fälschlich mit Integer.MIN_VALUE belegt hat, werfe das erste Bit… Gerade kompliziertere Operationen sind in einem Monoid sicher aufgehoben – hat man das einmal richtig hinbekommen, kann nichts mehr schiefgehen.




Follow

Erhalte jeden neuen Beitrag in deinen Posteingang.