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.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s