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.

Advertisements

5 Gedanken zu “Funktoren in Java

  1. Bei 1.) weiß ich nicht so richtig was du meinst. Habe ich etwas Gegenteiliges behauptet? Arrays fallen bei der Generics-Diskussion sowieso etwas aus der Rolle, weil sie sich völlig anders als z.B. Collections verhalten.

    2.) ist auch richtig, geht aber am Kern der Sache vorbei. Natürlich kann ich schreiben List<String>, aber ich kann nicht schreiben X<String>, und erst später (z.B. in einer Unterklasse) bestimmen, was genau X ist (also List oder Set oder WeakReference). Hier ist ein Blog-Beitrag mit „Pseudo-Java“, der deutlich zeigt, was in Java nicht geht (vergleiche einfach mal dessen Functor-interface mit meinem): http://blog.tmorris.net/higher-order-polymorphism-for-pseudo-java/

  2. Kennst du Functional Java? Das ist eine Bibliothek für funktionales Programmieren in Java, geschrieben von einigen derselben Leute, die auch für ScalaZ verantwortlich sind (z.B. Tony Morris, Jason „retronym“ Zaugg, Rúnar Óli Bjarnason, Tom Adams, Brad Clow, Ricky Clarkson und Nick Partridge).

    Dadurch, dass es sich um zwei Bibliotheken handelt, die von denselben Leuten zur Lösung desselben Problems in Scala und Java geschrieben wurden, ermöglichen sie wunderbare Vergleiche zwischen den beiden Sprachen.

    Interessanterweise fehlt die Funktor-Implementierung in Functional Java, während sie in ScalaZ vorhanden ist. Es würde mich nicht wundern, wenn die von dir angesprochenen Probleme (z.B. die Unfähigkeit über einen Typkonstruktor zu abstrahieren, also higher-kinded polymorphism) der Grund dafür wären.

  3. Ich habe beim FunctionalJava-Team deswegen nachgefragt. Tony Morris hat mir geantwortet:

    Hi Landei,

    These abstractions are of questionable value when it is not possible
    to write functions across them. I’ve not seen a way to make this
    happen without escaping out of the type system (i.e. reflection).
    Perhaps you have something that does (your provided lift does not
    exploit the higher-kind)

    While Functor is a fundamental abstraction, there are not many
    functions to run across it. However, one such function is flip:

    F<Func<A, B>>  => A => F<B>
    

    If we could write this function in a useful way, then your proposal
    would certainly have merit. Sadly, I’ve never found such a possibility
    (maybe you have?). I have my fingers crossed though!

    Das ist nachvollziehbar (ich habe ja schon selbst geschrieben, dass meine Implementierung nicht wirklich praktisch ist), und auf das gestellte Problem habe ich keine gute Antwort.

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