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

Schachteln für Fortgeschrittene

Angeregt von dieser Frage auf Stackoverflow will ich mich heute mit geschachtelten Listen beschäftigen: Kann man eine Methode schreiben, die sowohl eine Liste von Ints wie auch eine Liste von Int-Listen wie auch eine Liste von Listen von Int-Listen u.s.w. aufsummieren kann? Sicher, das geht auch in Java – allerdings nicht typsicher: Da es dort keine Möglichkeit gibt, einen allgemeinen „Listen-Stapel-Typ“ zu definieren, muss gecastet werden, und das wiederum heißt, das Laufzeitfehler auftreten können, wenn ein ungeeignetes Objekt (sagen wir eine String-Liste) übergeben wird.

Wie sieht die Haskell-Lösung aus?

class Summable a where
  total :: a -> Int

instance Summable Int where
  total = id  

instance Summable x => Summable [x] where
  total = sum . map total  

total ([[[1,2,3],[4,5]],[[6],[7,8,9,10]]] :: [[[Int]]])
--55

Aha, Typklassen! Wir definieren eine Typklasse „Summable“, die eine Funktion „total“ zum Aufsummieren enthält. Die Instanz für Int ist trivial: Wir geben einfach die Zahl selbst zurück (man hätte dafür auch total x = x schreiben können). Interessanter ist die Instanz für Listen, die eine sogenannte Context-Bound enthält: Wenn a in der Klasse Summable ist, dann ist auch eine Liste von a in der Klasse – genau die Art von „Rekursivität“, die wir brauchen. Deshalb darf man in der Definition von total auch die Funktion total auf die Elemente anwenden, da man ja weiß, dass sie auch Summable sind. In der letzten Zeile wird die Funktion ausprobiert (dass man u.U. die Typangabe :: [[[Int]]] braucht, hat nichts mit unseren Typklassen zu tun, sondern ist der „Monomorphismus-Restriktion“ geschuldet, und wäre bei nicht-numerischen Typen nicht notwendig).

Wie setzt man das nun in Scala um? Ich habe mich zuerst mit einer typklassenartigen Implementierung versucht, bin aber nicht so recht weitergekommen. Am Ende hat dann eine etwas direktere Vorgehensweise zum Ziel geführt:

object nestedTest {
  
  case class Summable(total:Int)
   
  implicit def intSummable(i:Int) = Summable(i)
  
  implicit def listSummable[T <% Summable](list:List[T]) = Summable(list.map(_.total).sum)
  
  def total[T <% Summable](t:T) = t.total
  
  def main(args: Array[String]) {
    println(total(1))
    println(total(List(1,2,3)))
    println(total(List(List(1),List(2,3))))
    //println(total(List(List("a"),List("b","c")))) 
    //--> error: No implicit view available from List[List[java.lang.String]] => nestedTest.Summable.
  }
}

Summable ist jetzt keine Typklasse, sondern einfach ein Wrapper um Int. Dann definiere ich entsprechende Konvertierungen. Wieder ist die Umwandlung von Int nicht besonders spannend, dafür die Definition der List-Variante. Der entscheidende Trick ist die Verwendung einer View-Bound T <% Summable. Das heißt, dass T in ein Summable "umwandelbar" sein muss, und genau das ist der Trick, um Scala die gewünschte "Rekursivität" beizubringen. Durch die Garantie der View-Bound ist es erlaubt, map(_.total) zu schreiben, denn wir wissen ja, dass T in ein Summable konvertiert werden kann, und Summable hat ein Feld namens total. Für die Bequemlichkeit definieren wir noch eine Top-Level-Funktion für total, um dem Anwender das Hantieren mit Summable zu ersparen. In der main-Methode werden nun verschiedene Varianten ausprobiert. Ein Aufruf mit einem unpassenden Argument scheitert, und das sogar mit einer recht verständlichen Fehlermeldung.

Ich hoffe, dass das Beispiel gezeigt hat, dass Scalas Typsystem dem von Java auch bei recht praktischen Aufgabestellungen überlegen ist, auch wenn man manchmal etwas frickeln muss. Haskell glänzt hier mit einer sehr einfachen Variante, aber es gibt auch Konstrukte, die sich besser mit Scala implementieren lassen (z.B. alles mit variabler Anzahl Argumente).

Ich fasse schon einmal den guten Vorsatz, das Blog nächstes Jahr nicht ganz so stiefmütterlich zu behandeln. An spannenden Themen soll es nicht mangeln: Da wäre das gerade frisch releaste Ceylon (allerdings mit noch enttäuschenden Funktionsumfang), Bauarbeiten an Scala und Java, die tolle Sprache Frege, die langsam erwachsen wird und ihr Vorbild Haskell, bei dem auch interessante Neuerungen anstehen, wenn man Simon Peyton Jones glaubt.

Dann wünsche ich allen ein Frohes Fest, einen Guten Rutsch und ein erfolgreiches 2012!

Frege – funktionale Programmierung auf der JVM

Gottlob Frege war ein deutscher Mathematiker und Logiker, der lange vor Alonzo Church über Funktionen mit Funktionen als Argumente nachdachte. Ein schöner Name für eine funktionale Programmiersprache.

Die Sprache Frege lehnt sich stark an Haskell an, nutzt aber nach Möglichkeit die Gegebenheiten der JVM aus. Interessanterweise folgt Frege nicht dem üblichen Ansatz, direkt zu Bytecode zu compilieren, es erstellt stattdessen erst Java-Klassen (die allerdings weniger zur Abendlektüre geeignet sind) und ruft für diese den Java-Compiler auf.

Die auffälligsten Unterschiede zu Haskell sind die Übernahme des Package-Prinzips und von Private-Modifiern (statt Exportlisten) sowie die Nutzung nativer Strings und Primitive. Einige syntaktische Seltsamkeiten von Haskell wurden gestrichen, aber insgesamt fallen die Unterschiede gering aus.

Die Auswahl an Bibliotheken ist überschaubar und auch das Prelude (das Analogon zum Package java.lang) weist noch einige Lücken auf. Trotzdem macht das Vorhandene einen recht soliden Eindruck, es ist genug Dokumentation zum Loslegen vorhanden und es macht Spaß, ein wenig mit Frege herumzuspielen. Wenn die Kernsprache erst einmal stabil ist, sollte es kein Problem sein, geeignete Haskell-Bibliotheken mit geringen Anpassungen zu übernehmen. Außerdem ist auch der Zugriff auf Java-Bibliotheken ebenfalls recht unkompliziert möglich.

Die vorhandenen Ansätze lassen einen umsichtigen Umgang mit Typklassen erkennen (z.B. werden Funktionen wie null oder length verallgemeinert, so dass sie nicht nur auf Listen arbeiten). Das lässt darauf hoffen, dass bei künftigen Erweiterungen der Typklassen-Hierarchie einige von Haskells Fehlern vermieden werden.

Frege ist eine interessante Alternative zu den anderen JVM-Sprachen, deshalb hoffe ich sehr, dass dieses ambitionierte Projekt vorankommt und sich eine Community herausbildet.

Applikative Funktoren in highJ

Heute will ich einmal ein kleines Beispiel bringen, wie man die highJ-Bibliothek verwenden kann. Das Beispiel in Haskell sieht harmlos genug aus:

import Control.Applicative

filter (and . ([ (>2) , (<7) , odd ] <*>) . pure) [1..10]
--[3,5]

Was passiert, ist ziemlich klar: Eine Liste von 1 bis 10 wird gefiltert, und zwar nach einer Reihe von Kritierien. Die filter-Funktion erwartet eigentlich nur ein einziges Kriterium, also stellt sich die Frage, wie der seltsame Ausdruck in der Mitte funktioniert.

Die pure-Funktion verpackt einen Wert in einen applikativen Funktor. Für eine Liste heißt das, das Argument wird zu einer ein-elementigen Liste. Der seltsame Operator <*> (auch ap genannt) führt in einen applikativen Funktor verpackte Funktionen auf in einen applikativen Funktor verpackte Argumente aus, z.B. ergibt [(>2), (<7), odd] <*> [7] den Wert [True,False,True]. Hätte man mehrere Argumente, würden alle möglichen Kombinationen aus einer der Funktionen und einem Argument ausgeführt und zu einer Liste zusammengefasst.

Man kann applikative Funktoren als Berechnungen in einem gewissen „Kontext“ ansehen: Dass z.B. eine Rechnung scheitern kann (Maybe, Either), dass eine Zustand verändert wird (State, IO) oder wie in unserem Fall mit Listen, dass es für eine Rechnung „mehrere Lösungen“ (wie etwa Nullstellen eines Polynoms) gibt, und diese Mehrdeutigkeit sozusagen mitgeschleift wird.

Hier nun die Umsetzung in highJ:

import fj.F;
import fj.data.List;
import highj._;
import highj.data.ListMonadPlus;
import highj.data.ListOf;
import highj.typeclasses.category.Applicative;

...

Applicative<ListOf> app = ListMonadPlus.getInstance();

F<_<ListOf,Boolean>, Boolean> and = new F<_<ListOf,Boolean>, Boolean>() {
     public Boolean f(_<ListOf, Boolean> wrappedList) {
        for(Boolean b : ListOf.unwrap(wrappedList)) 
            if (! b) return false;
        return true;
    }
};

F<Integer, Boolean> greaterThanTwo = new F<Integer, Boolean>() {
    public Boolean f(Integer a) { return a > 2; }
};

F<Integer, Boolean> lessThanSeven = new F<Integer, Boolean>() {
    public Boolean f(Integer a) { return a < 7; }
};

F<Integer, Boolean> odd = new F<Integer, Boolean>() {
    public Boolean f(Integer a) { return a % 2 == 1; }
};

_<ListOf, F<Integer, Boolean>> condList = 
        ListOf.list(greaterThanTwo, lessThanSeven, odd); 

List<Integer> result = List.range(1, 10).filter(
    app.<Integer>pure().andThen(app.ap(condList).andThen(and)));
//[3, 5]

Wer sich die Imports genau angesehen hat, wird feststellen, dass nicht nur die Klasse F für Funktionen, sondern auch die Klasse List aus der Functional-Java-Bibliothek stammt. Es handelt sich um eine unveränderliche, einfach verlinkte Liste, die sich (bis auf die Lazyness) ähnlich wie eine Haskell-Liste verhält, also hier besser als java.util.List geeignet ist.

Als erstes besorge ich mir den applikativen Funktor für Listen (ListMonadPlus implementiert zahlreiche Interfaces, darunter auch dieses). Wie im letzen Artikel ausgeführt, benötige ich eine Wrapper-Klasse ohne Typ-Parameter für meine Typklassen, hier ListOf. Danach definiere ich die Funktionen, die ich benötige. Natürlich ist dieser Teil sehr viel länger als in Haskell, und macht die Anwendung recht unhandlich. Ich kann mir aber vorstellen, dass das in bestimmten Fällen noch „erträglich“ ist, nämlich dann, wenn es eine recht übersichtliche Anzahl von Funktionen für ein bestimmtes Gebiet gibt, die man alle nur einmal irgendwo definieren und dann beliebig kombinieren kann. Und Java 8 verspricht hier mit der Lambda-Syntax Abhilfe.

Als nächstes packe ich meine drei Kriterien in eine Liste. Dann kann endlich der Aufruf erfolgen, und zwar fast so wie in Haskell. Die range- und andThen-Methoden stammen aus Functional Java, wobei letztere die beiden aus dem applikativen Funktor stammende pure- und ap- sowie die lokale and-Funktion miteinander kombiniert (oder genauer gesagt komponiert).

Natürlich war das nur ein Zipfelchen dessen, was möglich ist. Wie immer lohnt es nicht, mit so einer Framework-Kanone auf einen Beispiel-Spatzen zu schießen, sondern die Typklassen müssten schon einen wesentlichen Teil der Problem-Domäne abdecken, um einen Einsatz zu rechtfertigen. Dabei gibt es wirklich interessante Sachen: Neulich habe etwa ich ein Papier über die Anwendung von Biarrows gelesen, wodurch reversible Programmierung ermöglicht wird (wenn man z.B. mit dieser Technik einen Parser für eine Sprache schreibt, kann man damit auch „automatisch“ aus einem Syntaxbaum wieder Sourcecode erstellen). Vielleicht wäre highJ für solche oder ähnliche Projekte eine nützliche Ausgangsbasis.

Bevor ich es vergesse: Ich bitte um etwas Geduld, es wird hier auch bald wieder um Scala gehen. Das highJ-Experiment schlägt (auf Kosten der Praktikabilität) eine weite Brücke von Haskell nach Java, und ich denke, dass ich daraus einiges lernen kann – auch in Hinblick auf meine Fähigkeiten in Scala.

highJ: Haskell-Typklassen in Java

Heute will ich ein wenig über mein neuestes Projekt namens highJ schreiben. Eigentlich steht das „high“ für „higher kinded types“ (Typen höherer Ordnung), aber die Assoziation zu „highjack“ ist durchaus gewollt. Zum Thema Typen höherer Ordnung und Typklassen habe ich ja schon etwas geschrieben, deshalb soll es hier auch mehr um die Realisierung in Java gehen.

Ausgangspunkt meiner Reise war die Frustration, dass man nicht mal ein gescheites Funktor-Interface in Java schreiben kann, denn die dort vorgestellte Lösung funktioniert zwar, ist aber ziemlich „sperrig“, wie ich schon damals schrieb. Schon bei der nächsten Abstraktionsstufe, einem applikativen Funktor, versagte meine damalige Methode völlig. Im Rückblick verwundert es schon, dass ich zwar den Grund des Scheiterns verstand, aber lange nicht auf eine Lösung kam – wahrscheinlich weil ich einfach nicht akzeptieren wollte, dass in Java etwas wie List<T> in dieser Form niemals als Typ höherer Ordnung durchgehen würde. Der Trick ist, dass man die Liste nett verpacken muss.

Eigentlich ist es ganz logisch: In Java ist es kein Problem, wenn der Parametertyp T einer Liste nicht bekannt ist – das ist der allseits bekannte Typ-Polymorphismus erster Ordnung. Ein Funktor besteht aber im Kern aus einer Methode fmap, die ein X<A> nimmt und mit Hilfe einer übergebenen Funktion A -> B in ein X<B> umwandelt, wobei X eine Art Container (wie etwas List) ist. A und B sollen natürlich frei wählbar sein, also gehören sie als Typparameter zur fmap-Methode, und nicht zum Funktor selbst, sonst verliert das Konstrukt jegliche Flexibilität (wie bei meiner ursprünglichen Implementierung schön zu sehen ist). Und wer will schon für jede Kombination von A und B einen neuen Funktor erstellen müssen?

Gut, aber was passiert nun mit dem X? Dieses X muss natürlich ein Typparameter des Funktors werden, aber wie soll das gehen? Zu X gehört ja selbst ein Typparameter, und bei dem wollen wir uns nicht festlegen, denn er soll ja in der fmap-Methode einmal mit A und einmal mit B belegt werden. Aber betrachten wir das Problem einmal andersherum: Was ist, wenn X keinen Typparameter hätte? Versuchen wir einfach mal, einen Funktor zu schreiben:

//Pseudocode
public interface Functor<X>  {
    public <A, B> X?B fmap(F<A, B> fn,  X?A xa);
}

F ist hier natürlich einfach ein Funktions-Objekt, wie z.B. in der Bibliothek functionaljava. Die Frage ist, wie können wir X jeweils mit A oder B irgendwie verbinden? Die Antwort ist geradezu peinlich trivial: Wie brauchen ein Objekt, das sowohl X wie auch seinen Typparameter selbst als Typparameter hat. In highJ habe ich dieser Klasse einen etwas ungewöhnlichen Namen verpasst, nämlich nichts weiter als den Unterstrich. Der Grund wird schnell klar, wenn man viel Code lesen muss, der solche Signaturen enthält: Bereits ein Buchstabe wäre schon zuviel gewesen. Hier unsere neue Definition:

public interface Functor<X>  {
    public <A, B> _<X, B> fmap(F<A, B> fn,  _<X, A> xa);
}

Was ist nun im Unterstrich-Objekt gespeichert? Natürlich der „echte“ Typ, der durch X repräsentiert wird. Da das Unterstrich-Objekt aber zu allen möglichen X-Typen passen soll, bleibt uns nichts anderes übrig, als einfach ein Object zu verwenden:

//vereinfacht
public final class _<X,T> {
     private final Object data;

     public _(Object data) {
        this.data = data;
     }

     public Object read() {
        return data;
     }     
}    

Keine Angst, so unsicher habe ich es in highJ nicht implementiert, aber es geht hier ja nur um’s Prinzip. Wie würde nun eine Funktor-Implementierung für List aussehen? Zuerst brauchen wir unser X, dass wir ListOf nennen:

//vereinfacht
public final class ListOf  {
    public static <T> _<ListOf, T> wrap(List<T> list) {
        return new _<ListOf, T>(list);
    }
    
    public static <T> List<T> unwrap(_<ListOf, T> listWrapper) {
        return (List<T>) listWrapper.read();
    }
}

Die Klasse macht nicht mehr, als eine Liste ein- und wieder auszupacken. Beim Auspacken gibt es einen hässlichen Cast, aber in highJ ist dieser relativ sicher, denn ich habe einige Vorkehrungen getroffen, damit jedes X für seinen „eigenen“ Typen _<X,T> verantwortlich ist, und niemand anders ihn einpacken und auspacken darf. Wenn ListOf sicher sein kann, dass es seinem _<X,T> bei der Erzeugung eigenhändig eine List<T> mitgegeben hat, ist es auch „sicher“, dass beim Auspacken wieder eine List<T> drin ist. Wer natürlich hier mit Raw-Types oder Reflection zu tricksen versucht, ist selber schuld, wenn er auf die Nase fällt.

Nun als krönender Abschluss unsere Funktor-Implementierung für Listen:

public class ListFunctor implements Functor<ListOf>  {
    public <A, B> _<ListOf, B> fmap(F<A, B> fn,  _<ListOf, A> listA) {
        List<B> listB = new ArrayList<B>();
        for(A a : ListOf.unwrap(listA)) {
           listB.add(fn.f(a));
        }
        return ListOf.wrap(listB);
    }
}

Das ist der ganze Zauber, auf diesem Konzept beruht meine ganze Bibliothek. Nun könnte man einwenden, dass der ganze Aufwand mit dem Ein- und Auspacken die Sache unpraktikabel macht – und das habe ich anfangs auch gedacht. Der Clou ist aber, dass sich mit diesem Konzept Haskells Typklassen fast eins zu eins übersetzen lassen. Und das wiederum bedeutet, dass ein ganzes Arsenal an nützlichen Maschinen bereitsteht, mit dem so ein verpackter Wert bearbeitet werden kann – und dazu muss man ihn nur einmal am Anfang einpacken, und erst ganz am Ende wieder auspacken. Ich habe auch versucht, „Übersetzungsklassen“ wie ListOf komfortabler zu gestalten, was das Handling zumindest erträglich macht.

Neben dem bescheidenen Funktor gibt es inzwischen Bifunktoren, Monaden, Foldables, Arrows und vieles mehr. Als Datentypen verwende ich Klassen von functionaljava, und auch dort gibt es einige „Übersetzer“: ListOf, OptionOf, EitherOf, FunctionOf, PairOf. Ich bin übrigens selbst erstaunt, wie schnell die Bibliothek wächst. Das Ganze kommt mir manchmal fast etwas magisch vor: Ich brauche bloß den oft ziemlich unverständlichen Haskell-Code rein mechanisch nach Java zu übersetzten, und selbst so verrückte Sachen wie Kleisli-Arrows „funktioneren“ dann einfach. Und das wiederum gibt mir die Hoffnung, dass vielleicht am Ende doch etwas Nützliches bei der Sache herauskommen könnte. Ich habe jedenfalls meinen Spaß daran und lerne einige Ecken von Haskell kennen, die mir bisher völlig fremd waren.

Funktoren in Java

Was ist ein Funktor? Darauf gibt es mindestens zwei Antworten, denn das Wort wird mit unterschiedlichen Bedeutungen verwendet. Die erste, meiner Meinung nach völlig überflüssige Verwendung ist als hochgestochenes Synonym für etwas, das auch so schon genügend Bezeichnungen besitzt: Funktionsobjekt, Lambda, Closure u.s.w. Mich interessiert die zweite Bedeutung, die aus der Kategorientheorie kommt, und in diesem Sinne z.B. in Haskell oder Scala (genauer gesagt in der Scalaz-Bibliothek) verwendet wird. Dort ist ein Funktor einfach ein Apparat, der Eier in der Eierpackung kochen kann. Wie bitte? Hier ein Verfahren, das wir sicher alle so oder so ähnlich kennen:

List<String> strList = Arrays.asList(new String[]{"one","two","three"});
List<Integer> intList = new ArrayList<Integer>();
for(String s : stringList) {
   intList.add(s.length());
}
System.out.println(intList);
//--> [3, 3, 5]

Wie man sieht, müssen die Strings erst ausgepackt, die Funktion ausgeführt, und das Ergebnis wieder verpackt werden. Unsere „Verpackungen“ sind Listen, unsere „rohen Eier“ Strings, die „gekochten Eier“ Integers, und die length()-Methode das Eier-Kochen. Wenn meine obige „Definition“ stimmt, sollte also ein Listen-Funktor die ganze Aktion ohne das Aus- und Einpacken schaffen – man spricht dabei vom „Mappen“. In Scala wäre das dank Typen höherer Ordnung kein Problem, in Java hatte ich daran ziemlich zu knabbern, und das Ergebnis ist nicht überwältigend – aber immerhin lehrreich. Zuerst brachen wie ein Interface für eine „Funktion“:

public interface F<A,R> {
   public R apply(final A a);
}

Nun das Herzstück der ganzen Konstruktion, das Funktor-Interface:

public interface Functor<A, B, FromInstance, ToInstance> {
    public ToInstance fmap(F<A,B> f, FromInstance instance);
}

Was zum Teufel ist denn das? Nun, das war die einzige Möglichkeit, die ich gefunden habe, um einen Funktor typsicher in Java zu definieren. An einer Implementierung lässt sich das am Besten erklären:

public class ListFunctor<A, B> implements Functor<A, B, List<A>, List<B>> {

    @Override
    public List<B> fmap(F<A, B> f, List<A> instance) {
        List<B> result = new ArrayList<B>();
        for (A a : instance) {
            result.add(f.apply(a));
        }
        return result;
    }
}

Aha, FromInstance steht also für die „verpackten“ A-Elemente, und ToInstance für die „verpackten“ B-Elemente. Es gibt in Java weder die Möglichkeit auszudrücken, dass die Verpackungstypen für A und B zusammenpassen sollen (also z.B. beides Listen sein sollen), noch dass FromInstance den Typparemeter A und ToInstance den Typparameter B haben soll, solange man den konkreten Verpackungstyp nicht kennt. Deshalb muss man diese „Gleichsetzung“ bis in die implementierende Klasse aufschieben, da man dann ja weiß, um welchen Verpackungstyp es sich genau handelt.

Der große Nachteil meiner Implementierung ist, dass A und B Typparameter der Klasse sind. Das heißt, um so einen ListFunctor überhaupt benutzen zu können, muss er mit den korrekten Typen für A und B konstruiert werden, was nicht nur umständlich ist, sondern so ziemlich jede Wiederverwendbarkeitsbestrebung torpediert. Zumindest funktioniert der Code, und zwar typsicher und ohne Casts:

F<String,Integer> strLen = new F<String, Integer>() {
  public Integer apply(String a) {  return a.length(); }
};
List<String> strList = Arrays.asList(new String[]{"one","two","three"});
ListFunctor<String,Integer> lf = new ListFunctor<String,Integer>(); 
List<Integer> intList = lf.fmap(strLen, strList);
System.out.println(intList);
//--> [3, 3, 5]

Das ist meiner Meinung nach zu unbequem, um es im richtigen Leben zu verwenden. Ich habe aber einen kleine Erweiterung gefunden, mit dem Funktoren eventuell doch etwas nützlich sein können, nämlich durch das „Liften“ von Funktionen (wie „Mappen“ auch ein „Haskellismus“). Zuerst ein paar Bauarbeiten an F und einer abstrakten Klasse F1, die F implementiert:

public interface F<A,R> {
   public R apply(final A a);

   public <FromInstance, ToInstance> F<FromInstance, ToInstance> lift1(
           Functor<A,R,FromInstance, ToInstance> functor);
}

public abstract class F1<A, R> implements F<A, R> {

     public abstract R apply(final A a);

    @Override
    public <FromInstance, ToInstance> F<FromInstance, ToInstance> lift1(
           final Functor<A, R, FromInstance, ToInstance> functor) {
        return new F1<FromInstance, ToInstance>() {
            @Override
            public ToInstance apply(FromInstance fromInstance) {
                return functor.fmap(F1.this, fromInstance);
            }
        };
    }
}

Und nun der Zaubertrick: Mit einem geeigneten FooFunctor kann man jetzt aus jeder beliebigen Funktion F<A,B> eine F<Foo<A>, Foo<B>> zaubern:

F<String,Integer> strLen = new F1<String, Integer>() {
    public Integer apply(String a) { return a.length(); }
};

//Simsalabim!
F<List<String>,List<Integer>> strLenLifted =
        strLen.lift1(new ListFunctor<String,Integer>());

List<String> strList = Arrays.asList(new String[]{"one","two","three"});
List<Integer> intList = strLenLifted.apply(strList);
System.out.println(intList);
//--> [3, 3, 5]

Das ist schon ein wenig nützlicher, wenn man strLenLifted öfter gebrauchen kann. Trotzdem bleibt die Bedienung immer noch sperrig.

Was sind nun eigentlich alles Funktoren? Erst einmal so ziemlich alles „collection-artige“. Dann sind Haskells Monaden (wie z.B. IO) auch Funktoren, was für uns weniger von Interesse sein dürfte. Aber auch Funktionen selbst (also F in unserem Beispiel) sind ein Beispiel für Funktoren, aber wenn ich zu sehr darüber nachdenke, bildet sich ein Knoten in meinem Gehirn.

Ich sollte noch erwähnen, dass jeder ehrliche Funktor zwei Gesetzen folgen muss, die aber unmittelbar einleuchten. Erstens: Wird an fmap die Identitätsfunktion f(x) = x übergeben, kommt derselbe Funktor heraus wie der, den man hereinsteckt. Zweitens: Das Hintereinander-Ausführen zweier Mapping-Operationen mit den Funktionen f(x) = y und g(y) = z führt zum gleichen Ergebnis wie ein Mapping mit der „kombinierten“ Funktion g(f(x)) („Funktionskomposition“).

Die „nächst-mächtigere“ Erweiterung von Funktoren sind Applikative Funktoren (dort sind nicht nur die Werte, sondern auch die Funktionen „verpackt“), die viele interessante Eigenschaften und Anwendungen haben, sich aber anscheinend mit dem hier vorgestellten Ansatz nicht in Java modellieren lassen.

Vielen Dank an Sergey Tachenov und den anderen, die mir auf Stackoverflow bei meinen Versuchen weitergeholfen haben! Es hat viel Spaß gemacht, sich einmal aus Jux und Tollerei mit Javas Typsystem anzulegen, auch wenn ich immer nicht so richtig sagen kann, wer nun eigentlich gewonnen hat…

Nachtrag

Während die Typ-Signatur von Functor prinzipiell lästig ist, kann sie gerade durch ihre „Allgemeinheit“ recht flexibel sein, weil man damit recht frei definieren kann, was eine „Verpackung“ ist. Z.B. kann man einen String als „Verpackung“ für chars ansehen:

public class StringFunctor implements Functor<Character, Character, String, String>{

    @Override
    public String fmap(F<Character, Character> f, String instance) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < instance.length(); i++) {
            sb.append(f.apply(instance.charAt(i)));
        }
        return sb.toString();
    }
}

Mit diesem Funktor lassen sich beispielsweise alle „zeichenweisen“ Ersetzungen (etwa eine Umwandlung in Kleinbuchstaben oder eine Cäsar-Verschlüsselung) realisieren.

Und der „hirnverknotende“ Funktions-Funktor entpuppt sich in seinem Kern als einfache Funktions-Komposition:

public class FunctionFunctor<A,B,R> implements Functor<A,B,F<R,A>,F<R,B>> {

    @Override
    public F<R, B> fmap(final F<A, B> f, final F<R, A> instance) {
        return new F1<R, B>() {

            @Override
            public B apply(R r) {
                return f.apply(instance.apply(r));
            }
        };
    }
}

Wobei es hier wesentlich bequemer wäre, F einfach eine compose-Methode zu spendieren – aber immerhin funktioniert es.

Nochmal die Damen

Die berühmten 8 Damen hatte ich schon mal abgehandelt, aber das folgende Stückchen Haskell hat es mir angetan:

--http://www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

Das sieht ein ganzes Stück besser aus als mein eigener Versuch, und die Logik dahinter ist bestechend einfach: safe testet, ob zwei Positionen „sicher“ sind (sich also nicht in der gleichen Reihe, Spalte oder Diagonale befinden). qu nimmt eine Liste mit allen Teillösungen für die Reihen kleiner als k, und prüft dann für jede Liste qs, welche Spalten j in der Reihe k „sicher“ sind, und sammelt alle entsprechenden Listen mit den neuen Positionen. Nun wird qu für 1 bis n aufgerufen, und dabei jeweils die Teillösung des letzten Aufrufs übergeben, was man mit foldr realisieren kann.

Und hier meine Scala-Übersetzung, die sich wieder möglichst nah ans Original halten soll:

object queens {

   def nqueens(n: Int) = {
      import math.abs
      type Pos = (Int, Int)
      def safe(p:Pos, q:Pos) = p._1 != q._1 && p._2 != q._2 && abs(p._1 - q._1) != abs(p._2 - q._2)
      def qu(k: Int, qss:List[List[Pos]]) = 
        for(qs <- qss; j <- (1 to n) if qs.forall(safe(_ ,(j,k)))) yield ((j,k) :: qs)
      (1 to n).foldRight(List(List[Pos]()))(qu)
   }

   def main(args:Array[String]) = println(nqueens(8).mkString("\n"))
}

Zuerst importiere ich die abs-Methode und definiere den Typ (Int,Int) als Pos, weil ich ihn häufiger benötige. Lokale Hilfsfunktionen schreibt man in Scala besser zuerst, so dass man im Beispiel die umgekehrte Reihenfolge wie in Haskell hat. Bei safe gibt es kaum eine Änderung, wenn man davon absieht, dass in Scala leider kein Pattern Matching in der Argumentliste funktioniert. Die Methode qu wird im Prinzip unverändert übernommen, auch wenn die Syntax deutlich abweicht. Ich denke man sieht hier gut, wie stark Haskell den Entwurf von Scala beeinflusst hat, auch wenn man das Scala nicht unbedingt auf den ersten Blick ansieht. Zu guter Letzt kommt der Aufruf von qu über foldRight. In Scala ist foldLeft üblicher und auch performanter (da Haskell „lazy“ ist, scheint es dort umgekehrt zu sein), aber ich will ja dicht am Original bleiben. Da die Argumente für qu in der richtigen Reihenfolge geliefert werden, läßt sich das (k,l) => qu(k,l) wahlweise mit qu(_,_) oder schlicht mit qu abkürzen. Die main-Methode testet den klassischen 8×8-Fall.

Wie ich schon im oben genannten Artikel erwähnt habe, kann man mit Scala normalerweise sehr dicht an einer Vorlage in einer funktionalen Sprache wie Haskell, Clean oder ML bleiben. Natürlich wird durch die unvollständige Typinferenz und ausführlichere „Zeichensetzung“ in Scala alles ein wenig länglicher, aber strukturell ähneln sich die beiden Programme sehr stark. Auch die „Werkzeugkisten“ der beiden Sprachen haben viel gemeinsam, während Dinge wie Tupel, foldRight, Pattern Matching und List Comprehensions in Java fehlen.

So, in Zukunft werde ich die Damen in Ruhe lassen, zumindest hier im Blog… Hatte ich eigentlich schon erwähnt, dass ich Single bin? 😛

Artikel über Typklassen in Scala

Typklassen sind ein nützliches Feature in funktionalen Sprachen wie Haskell. Dabei handelt es sich nicht um Klassen im objektorientierten Sinne, sondern um eine Art Äquivalenzklassen von Operationen. Will man z.B. in Java oder Scala Algorithmen oder Datenstrukturen implementieren, die das Konzept einer Ordnungsrelation benötigen, greift man auf Interfaces bzw. Traits wie Comparable oder Ordered zurück – was den großen Nachteil hat, dass man einen Datentyp nicht nachträglich diese Eigenschaft verpassen kann, wenn man dessen Quellcode nicht kennt. Haskell geht sozusagen umgekehrt vor, es definiert nachträglich, welche Datentypen irgendwie geordnet sind (und wie die entsprechenden Methoden dazu implementiert sind). Diese Technik ist also wesentlich flexibler als Vererbung: In einem gewissen Sinne ist es so, als ob man einer bestehenden Klasse nachträglich ein Interface (mit entsprechend implementierten Methoden) „ankleben“ könnte.

Nun ist Scala im Gegensatz zu Java ausdrucksstark genug, um dieses interessante Feature recht einfach zu imitieren, und anstatt selbst herumzustümpern verweise ich einfach auf ein paar interessante Artikel zu diesem Thema:

Nebenbei möchte ich nicht versäumen, auf den Release Candidate 7 für Scala 2.8 hinzuweisen, insbesondere da es aus gutunterrichteten Kreisen heißt, dass in etwa ein, zwei Wochen Scala 2.8 kommen wird, wenn nicht ein wirklich böser Bug sein häßliches Haupt erhebt. Das finde ich spannender als Deutschland gegen Argentinien…

Wie funktional ist Scala?

Nachdem ich ein wenig über die funktionale Sprache Clean gelesen hatte, wollte ich auch mal ein Beispiel selber programmieren. Das fiel mir erstaunlich leicht, denn Clean ähnelt der Sprache Haskell, mit dem ich auch schon ein wenig herumgespielt habe. Das Ergebnis ist sicher kein Meilenstein funktionaler Programmierung, aber das Programm läuft. Hier sind also meine acht Damen in Clean:

//Clean 2.2
module Queens
import StdEnv

Start = queens []

queens list 
    | length list == 8 = [list]
    | otherwise = flatten (map (\x = queens [x:list]) (filter (valid list) [1..8]))
    where 
    valid t h = not (isMember h t || diagonal (+) (h+1) t || diagonal (-) (h-1) t)
        where
        diagonal _ _ [] = False
        diagonal op n [h:t] = n == h || diagonal op (op n 1) t

So sieht Code aus, mit dem man OO-Programmierer erschrecken kann. Aber mit ein paar zusätzlichen Informationen klärt sich das Bild: Ergebnis der Berechnung soll eine Liste von Int-Listen sein. Dabei hat jede Int-Liste acht Stellen und gibt eine Brettposition wieder (die n-te Zahl gibt dabei an, in welcher Spalte die Dame in der n-ten Reihe steht). Hat unsere Liste die gewünschte Länge 8, sind wir fertig. Andernfalls (otherwise) nehmen wir die Spaltenpositionen von 1 bis 8, behalten nur die, die nicht von den vorangegeangenen bedroht werden (filter(valid list)), fügen die jeweilige Position an die vorhandene Liste, rufen damit Queens rekursiv auf und liefern die Ergebnisse der einzelnen Aufrufe zusammengefügt (flatten) zurück. Die Unterfunktion valid hat drei Bedrohungsarten zu berücksichtigen: gleiche Spalte und gleiche Diagonale aufsteigend oder absteigend. Für die Diagonalen gibt es eine Unter-Unterfunktion diagonal, bei der auch der Operator mitgeliefert wird, der die Richtung der Diagonale bestimmt (also, ob zur vorhandenen Position +1 oder -1 in der nächsten Zeile gerechnet wird). Eigentlich ganz logisch, wenn man sich nicht von der Syntax erschrecken lässt.

Nun wird Scala oft als objektorientierte Sprache mit etwas funktionalem Flair beschrieben. Das ist auch wenig verwunderlich, schließlich läuft Scala auf der JVM, und die Kompatibilität zu Java wird (zu recht) immer wieder betont. Codeschnipsel, die Scala als „besseres Java“ propagieren sollen, tun ein übriges, um dieses Bild zu festigen. Dabei wird übersehen, dass Scala viel, viel weiter in Richtung funktionaler Programmierung geht als andere gebräuchliche OO-Sprachen, und damit meiner Meinung nach ziemlich genau in der Mitte zwischen den Paradigmen steht. Wie sieht nun mein Beispiel in Scala aus, wenn ich versuche, mich möglichst dicht ans Original zu halten?

object Queens {
  def main(args: Array[String]) { println(queens(Nil)) }
   
  def queens(list: List[Int]):List[List[Int]] = list match {
    case full if full.size == 8 => List(full)
    case _ => def valid(t:List[Int])(h:Int) = {
        def diagonal(op: (Int,Int)=>Int, n:Int, li:List[Int]): Boolean = li match {
          case Nil => false
          case h :: t => n == h || diagonal(op, op(n,1), t)
        }
        ! (t.contains(h) || diagonal(_+_, h+1, t) || diagonal(_-_, h-1, t))
      }
      (1 to 8 toList).filter(valid(list)).map(n => queens(n :: list)).flatten
  }
}

Ich finde, das sieht ziemlich ähnlich aus. Scala hat im Gegensatz zu Haskell und Clean nur eine partielle Typinferenz (der übliche Hindley-Milner-Algorithmus verträgt sich mit OO und vor allem Methodenüberladung nicht), so dass die Aufruftypen und bei rekursiven Funktionen auch die Rückgabetypen angegeben werden müssen. Lokale Funktionsdefinitionen funktionieren ähnlich wie das originale where, wobei man die lokale Funktion besser vor der Benutzung definiert. Der rekursive Aufruf von queens verwendet die gleichen Funktionen wie das Original. In diesem Fall finde ich, dass die objektorientierte Schreibweise vorteilhafter ist: Nimm die Positionsliste, filtere sie nach gültigen Positionen, rufe queens mit der um die jeweilige neue Position ergänzte Liste rekursiv auf, und füge die Ergebnisse zusammen. Man erhält also eine Abarbeitungsreihenfolge in Leserichtung, und nicht umgekehrt.

Der vorgestellte Code zeigt, wie weit man sich in Scala von Java wegbewegen kann, denn dort könnte man nicht einmal annähernd etwas ähnliches schreiben. Wenn man es will, ist mit Scala ein sehr funktionaler Stil möglich, nicht ganz wie in Haskell oder Clean, aber doch sehr dicht dran. Aber das Schöne ist, dass man dazu nicht gezwungen wird. Es ist immer gut, wenn man sich entscheiden kann. Funktionale Programmierung ist keine „Silver Bullet“, aber es lohnt, sich damit zu beschäftigen.

Nachtrag:
Martin Odersky hat gerade einen Artikel veröffentlicht, in dem er Scala als „postfunktionale Sprache“ bezeichnet, und auch auf andere Diskussionen um Scalas „Funktionalität“ verweist. Die neue Bezeichnung gefällt mir. Und Java könnte man dann unter den „dysfunktionalen Sprachen“ einordnen 😀

Mit sieben Sieben sieben …

Nachdem ich schon im Beitrag „Der Weg ist das Ziel“ Code von Java nach Scala „übersetzt“ habe, probiere ich es diesmal mit einer funktionalen Sprache, nämlich Haskell – nicht dass ich Haskell wirklich beherrschen würde, aber dafür reicht es gerade so.

Ausgangspunkt ist der wirklich lesenswerte Artikel The Genuine Sieve of Eratosthenes“ von Melissa E. O’Neill, in dem sie aufzeigt, dass das, was vielen Informatik-Studenten als Sieb des Eratosthenes verkauft wird, gar nicht der originale Algorithmus – der mit dem Abstreichen – ist, sondern ein zwar kurzes und elegant wirkendes, dafür aber hoffnungslos ineffizientes Plagiat. Nun ist es trivial, den originalen Algorithmus zu implementieren, wenn man vorher weiß, bis zu welcher Schranke die Primzahlen berechnet werden sollen. Deshalb stellt die Autorin eine clevere Implementierung vor, die das Durchstreichen sozusagen „just in time“ durchführt.

Setzen wir also die elaborierteste Version (zu finden auf Seite 7 und 8 des Papiers) nach Scala 2.8 um:

object primes {

type SI = Stream[Int]

def sieve:SI = {
def wheel2357:SI = Stream(4,2,4,6,2,6,4,2,4,6,6,
2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,
6,4,2,4,6,2,6,4,2,4,2,10,2,10,2) append wheel2357
def spin(s:SI, n:Int):SI = Stream.cons(n, spin(s.tail, n + s.head))

case class It(value:Int, step:Int) {
def next = new It(value + step, step)

def atLeast(c:Int):It =
if (value >= c) this
else new It(value + step, step).atLeast(c)
}

implicit object ItOrdering extends Ordering[It] {
def compare(thiz:It, that:It) = {
val r = thiz.value – that.value
if (r == 0) thiz.step – that.step else r
}

}

import scala.collection.immutable.TreeSet

def sieve(cand:SI, set:Set[It]):SI = {
val c = cand.head
val set1 = TreeSet[It]() ++ set.dropWhile(_.value < c) ++ set.takeWhile(_.value < c).map(_.atLeast(c)) if (set1.elements.next.value == c) { val set2 = TreeSet[It]() ++ set1.dropWhile(_.value == c) ++ set1.takeWhile(_.value == c).map(_.next) sieve(cand.tail, set2) } else { Stream.cons(c, sieve(cand.tail, set1 + It(c*c,2*c))) } } Stream(2,3,5,7,11) append sieve(spin(wheel2357,13), new TreeSet[It] + It(121,22)) } def main(args:Array[String]) { sieve.takeWhile(_ < 1000).foreach(println) } } [/sourcecode] Dieser Code versucht, möglichst dicht am Original zu bleiben. Wie immer sieht der ganze Apparat viel furchterregender aus, als er eigentlich ist. Ich kann hier nur einen kurzen Überblick geben und empfehle, das sehr verständlich geschrieben Original-Papier zu lesen, bei dem die Ideen dieses Algorithmus Schritt für Schritt abgeleitet werden. Die Zeile type SI = Stream[Int] führt einen Typ-Alias für Integer-Streams ein, denn wir benutzen sie hier wirklich oft, nämlich überall, wo in Haskell Listen verwendet wurden (die vom Verhalten her mehr mit Streams gemein haben als mit Scala-Listen). Wer genau hinschaut wird erkennen, dass das "Wheel" einen Schritt weiter gedreht ist als im Original - mehr dazu später. Das Wheel optimiert alle Kandidaten-Zahlen weg, die bereits durch 2, 3, 5 oder 7 teilbar sind. Dazu speichert es die Schrittweiten zum jeweis nächsten möglichen Kandidaten. So kann in der Methode spin() ganz einfach ein Stream erzeugt werden, der nur Zahlen mit größeren Primfaktoren als 2, 3, 5 und 7 enthält. Nun kommt die Fallklasse It (für "Iterator"). Wenn wir eine neue Primzahl gefunden haben, erzeugen wir für diese ein neues It-Objekt, was dann später alle Vielfachen dieser Primzahl "just in time" eliminiert. Dazu werden bei jeder neuen Kandidatenzahl alle Its, die kleiner dieser Zahl sind, hochgesetzt. Gibt es danach mindestens ein It, das auf unserer Kandidatenzahl "landet", ist diese zusammengesetzt. Wurde unser Kandidat dagegen von allen kleineren Its "übersprungen", ist dieser eine neue Primzahl. ItOrdering wird gebraucht, um die Its immer sortiert halten zu können. Als implizites Objekt muss man es nicht übergeben, sondern es fungiert als eine Art "Default" für alle "interessierten" Methoden oder Klassen (in unserem Fall TreeSet). Dazu müssen diese einen entsprechenden impliziten Parameter vereinbaren, der dann automatisch "gefüllt" wird - wobei es natürlich auch erlaubt ist, einen normalen Parameter mitzugeben, um ein anderes als das Standard-Verhalten zu erzwingen. Im Original-Papier wird eine Priority-Queue verwendet. Auch Scala hat eine Implementierung, aber im Unterschied zur Haskell-Version ist diese veränderlich und unterstützt auch nicht das wahlfreie Löschen von Elementen. Als "Ersatz" muss deshalb hier ein TreeSet herhalten. In einer ernsthaften Implementierung würde man wahrscheinlich besser mit einer eigenen Implementierung fahren. Man sieht auch, dass das Hantieren mit dem TreeSet nicht besonders elegant aussieht und demnach eine "maßgeschneiderte" Lösung sehr zur Übersichtlichkeit beitragen könnte. Am Ende wird ein wenig "Setup" betrieben und die innere sieve-Methode - das eigentliche Arbeitstier - gestartet. Dabei ist im Gegensatz zur Original-Version schon die Primzahl 11 (und ihr entsprechendes It-Objekt) vorhanden, weil der Umgang mit einem eventuell leeren Set umständliche Fallunterscheidungen erfordert hätte. Das ist auch der Grund, warum das Wheel bei 13 und nicht bei 11 beginnt. Alles in allem war es eine sehr interessante Sache, Haskell-Code in Scala abzubilden, und auch wenn er jetzt nicht mehr ganz so elegant ist, kann man doch noch die Ausgangsversion recht gut wiedererkennen. Auf eine derartige Implementierung mit verschachtelten Streams wäre ich bestimmt nicht von allein gekommen. Ich hoffe, dass dieser Beitrag nicht zu mathematisch geraten ist, und würde mich natürlich über Verbesserungsvorschläge freuen.