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.

Werbeanzeigen

Abstrakte Kunst

Heute möchte ich über Abstraktion mit Traits sprechen, und auch die Verwendung von abstrakten Type-Members, die ich schon hier vorgestellt hatte, mit einem (hoffentlich) etwas geeigneterem Beispiel vertiefen.

Angenommen, man hat die Aufgabe, Prim’s Algorithmus zur Berechnung von minimalen Spannbäumen in ungerichteten Graphen zu implementieren. Aber sollte man den Algorithmus fest verdrahten? Es kommt natürlich auf den jeweiligen Kontext an, aber wenn nichts dagegen spricht, kann es nicht schaden, auch Platz für andere Implementierungen zu lassen, etwa Kruskal’s Algorithmus.

Nun stellt sich die Frage, wie wir unseren Graph repräsentieren wollen. Haben wir eine eigene Graph-Klasse? Oder einfach eine Adjazenz-Matrix? Wenn ja, sollen wir Arrays verwenden oder doch lieber eine Implementierung für schwach besetzte Matritzen? Nun, die eleganteste (wenn auch nicht performanteste) Antwort darauf ist: Es sollte uns völlig egal sein! Und weil man es meiner Meinung nach nicht oft genug wiederholen kann, sage ich es auch nochmal: Es sollte uns völlig egal sein! Wenn wir ein paar grundlegende Operationen auf unserem Graph ausführen können, reicht das für unseren und – potentiell – viele andere Algorithmen aus. Wir abstrahieren!

Bauen wir uns ein Trait, das Typen für einen Graphen sowie seine Knoten und Kanten definiert, und dazu ein paar nützliche Operationen:

//Scala 2.8
import scala.collection.immutable._

trait GraphAdapter {
    type G; //Graph
    type V; //Knoten (Vertex)
    type E; //Kante (Edge)
    def vertexList(g:G):Traversable[V]
    def edges(vertex:V, g:G):Traversable[E]
    def vertices(edge:E, g:G):(V,V)
    def getEdgeOrdering(g:G):Ordering[E]
}

Die Typen habe ich als abstrakte Type-Members repräsentiert, obwohl auch Generics möglich gewesen wären. Aber GraphAdapter soll ja gerade die Abhängigkeit von einer bestimmten Graph-Implentierung beseitigen, insofern schien es mir aus „philosophischer Sicht“ nur konsequent, die Typen auch zu „verstecken“. Die aufgelisteten Operationen sind nicht wirklich überraschend, außer vielleicht die letzte: Ordering ist die Scala-Spezialisierung von Java’s Comparator. Für die Berechnung des minimalen Spannbaums braucht man nämlich gar nicht die konkreten Abstände der Knoten, sondern es reicht schon aus, wenn man zwei beliebige Kanten miteinander vergleichen kann (totale Ordnung). Die Rückgabetypen wurden möglichst allgemein gehalten: Statt Set, List u.s.w. wurde deshalb das Supertrait Traversable verwendet.

Wie sieht nun eine konkrete Implementierung aus? Hier eine ziemlich krude Version für Adjazenz-Matrizen:

trait AdjacenceMatrix extends GraphAdapter {
    type G = Array[Array[Option[Int]]]
    type V = Int
    type E = (Int, Int)
    def vertexList(g:G):Traversable[V] = (0 until g.length).force
    def edges(v:V, g:G):Traversable[E] =
       g(v).zipWithIndex.filter(_._1 != None).toList.map(w => (v min w._2, v max w._2))
    def vertices(edge:E, g:G):(V,V) = edge
    def getEdgeOrdering(g:G) = new Ordering[E] {
       def compare(x:E, y:E) = {
           g(x._1)(x._2).get - g(y._1)(y._2).get
       }
    }
}

Knoten sind einfach Ints, Kanten sind Tupel zweier Knoten. Die zweidimensionale Matrix hat allerdings nicht Int als Elementtyp, sondern Option[Int]. Dadurch können „nicht vorhandene Verbindungen“ durch None gekennzeichnet werden, so dass man nicht auf gefährliche „magische Werte“ (wie -1 oder Integer.MIN_VALUE) zurückgreifen muss. Die edges-Implementierung sieht komplizierter aus, als sie eigentlich ist, was der wenig objektorientierten „low-level“ Repräsentation unseres Graphen geschuldet ist.
Die hier verwendete Implementierung ist ziemlich fragil, denn es wird einfach vorausgesetzt, dass die Matrix quadratisch und symmetrisch ist. Für unser Beispiel ist das nicht weiter schlimm, trotzdem sollte man das für ernsthafte Anwendungen nicht unbedingt nachahmen.

Nun schreiben wir ein Trait, das für einen gegebenen Graph-Adapter den Spannbaum berechnet. Damit wir schön abstrakt bleiben, wenn wir den Algorithmus einmal austauschen wollen, haben wir auch ein „abstraktes“ Supertrait:

trait MinimalSpanningTree  {
    self:GraphAdapter =>
    def minimalSpanningTree(g:G):Traversable[E]
}

trait PrimMST extends MinimalSpanningTree {
    self:GraphAdapter =>
    def minimalSpanningTree(g:G):Traversable[E] = if(vertexList(g).isEmpty) List[E]() else {
        implicit val edgeOrder:Ordering[E] = getEdgeOrdering(g)
        val vList = vertexList(g)
        val edgeSet = vList.foldLeft(TreeSet[E]())((e,v) => e ++ edges(v,g))
        def loop(vIn:Set[V], vOut:Set[V], mst:Set[E], eOut:Set[E]):Set[E] =
        if (vOut.isEmpty) mst else {
            val newE = eOut.find(e => vIn.contains(vertices(e,g)._1) ||
                vIn.contains(vertices(e,g)._2)).getOrElse(error("disconnected graph"))
            val newV = if (vIn.contains(vertices(newE,g)._1)) vertices(newE,g)._2
                       else vertices(newE,g)._1
            val new_vOut = vOut - newV
            loop(vIn + newV, new_vOut, mst + newE, eOut.filter(e =>
                new_vOut.contains(vertices(e,g)._1) || new_vOut.contains(vertices(e,g)._2)))
        }
        loop(Set(vList.head), Set[V]() ++ vList.tail, Set[E](), edgeSet)
    }
}

Auf die Details des Algorithmus will ich gar nicht weiter eingehen – einen Schönheitspreis wird meine Implementierung bestimmt nicht gewinnen. Die Grundidee ist recht einfach und wird im Wikipedia-Artikel sehr anschaulich dargestellt. Wichtig ist in unserem Beispiel der „Selbsttyp“, das self:GraphAdapter => am Anfang: Damit sagt man dem Trait, dass es nur zu einem GraphAdapter „hinzugemixt“ werden darf. Theoretisch könnte man stattdessen auch Vererbung verwenden, aber das wäre semantisch falsch: Der Algorithmus ist kein GraphAdapter, er arbeitet auf einem. Entsprechend werden die GraphAdapter-Operationen auch nicht implementiert, sondern nur benutzt.

Wofür nun der ganze Aufwand? Wir haben damit den Grundstein gelegt für einen kleinen Baukasten, mit dem man nach Lust und Laune Graphen und Algorithmen zusammenstöpseln kann, und es dann „einfach funktioniert“:

val calc = new AdjacenceMatrix with PrimMST 
val data = Array(Array(None,    Some(2), Some(2), Some(4)),
                 Array(Some(2), None,    Some(3), None ),
                 Array(Some(2), Some(3), None,    Some(5)),
                 Array(Some(4), None,    Some(5), None))
println(calc.minimalSpanningTree(data))
//--> Set((0,2), (1,2), (0,3))

Ich bin sicher nicht der einzige, dem das erst einmal „ein bisschen zu magisch“ vorkommt. Aber gehen wir in uns: Hatten wir nicht alle schon Fälle, wo wir uns geärgert haben, dass diese verdammt komplizierte und clevere Methode, die unser Kollege geschrieben hat, nur mit ints und nicht mit doubles arbeitet? Oder dass diese nützliche Bibliothek leider nur ihre eigenen Datentypen verwendet, die man erst einmal mühselig „von Hand“ füllen muss? Hatten wir noch nie Schmerzen bei einem Refactoring, bei dem ein grundlegender Datentyp des Systems geändert werden musste, und damit alles und jedes, was mit ihm irgendwie in Verbindung stand? In solchen und ähnlichen Situationen hätte uns eine abstraktere Implementierung das Leben sehr erleichtert, und Scala hätte uns wiederum bei der Implementierung dieser Abstraktion sehr geholfen.

Unser Beispiel ist auch in anderer Hinsicht interessant: Es wurden keine Klassen verwendet, nur Traits. Sicher, ich hätte z.B. aus AdjacenceMatrix auch eine abstrakte Klasse machen können. Aber Traits erlauben durch die „Zusammensteckbarkeit“ (a.k.a. Mixin-Komposition) eine erstaunliche Flexibilität – etwas, mit dem man als „einfach-vererbender“ Java-Programmierer erst einmal lernen muss umzugehen. Wenn man keine Konstruktor-Argumente übergeben muss, spricht in Scala kaum etwas dagegen, ein Trait zu verwenden.

Unser Beispiel ist nur eine von den vielen Abstraktions-Möglichkeiten, die Scala bietet. Wer Scala nur als „besseres Java“ verwendet, verpasst solche Chancen zu höherer Abstraktion. Natürlich sollte man nicht den Fehler machen, auf Teufel komm raus bis in die Stratosphäre hinein zu abstrahieren, denn wie heißt es so schön: Das Gegenteil eines Fehlers ist wieder ein Fehler. Aber da, wo Abstraktion wirklich gebraucht wird, kann sie unheimlich nützlich sein.

Ich hoffe nur, dass meine Ausführungen jetzt nicht zu abstrakt waren… 😀