Dependency Injection mit der Reader-Monade

Schon wieder nehme ich das böse M-Wort in den Mund! Dabei ist die Reader-Monade kaum mehr als eine einfache Function. Aber eins nach dem anderen.

Zuerst einmal das Datenmodell mit einem Fake-Service:

public class User {
    public long id;
    public String name;

    public User(String name, long id) {
        this.id = id;
        this.name = name;
    }
}

public interface UserService {
    User getUser(long id);

    List<User> findAll();
}

public class UserServiceImpl implements UserService {
    @Override
    public User getUser(long id) {
        return new User("user" + id,id);
    }

    @Override
    public List<User> findAll() {
        return IntStream.of(1,2,5,42).
               mapToObj(this::getUser).
               collect(Collectors.toList());
    }
}

Nun das Grundgerüst der Komponente, die diesen Service gern benutzen würde:

public class UserComponent {
    public User getUser(long id) { ??? }
    public String greet(User user) { ???  }
    public List<User> getAllUsers() { ??? }
    public String greetAll() { ??? }
}

Ohne den UserService läuft natürlich nichts, und wir wollen ihn auch nicht mit gewöhnlichen DI-Frameworks hineinzaubern. Welche Möglichkeiten haben wir dann?

Am naheliegendsten ist sicher, den Service im Konstruktor mitzugeben und in einer Instanzvariable zu speichern. Das Problem dabei ist, dass dann nur dort Objekte konstruiert werden können, wo der „richtige“ Service bekannt ist. Andere benötigte Klassen, die ebenfalls den Service benötigen, müssen als weitere Parameter übergeben werden (was die Initialisierung verkompliziert), oder im Konstruktor initialisiert werden (was zu unschönen Abhängigkeiten führt).

Weiterhin könnte man einfach jeder Methode den Service als Parameter mitgeben, also UserComponent.getUser(long id, UserService service). Das funktioniert, wird aber schnell ziemlich unschön, da dieser Parameter bei jedem einzelnen Aufruf „mitgeschleift“ werden muss.

Wir haben auch eine weitere Möglichkeit, nämlich keinen Wert, sondern eine Funktion zurückzuliefern, als wenn wir sagen wollten: Wenn du uns einen UserService gibst, können wir dir den Wert berechnen: Function getUser(long id).

Mit etwas „Verfeinerung“ ist das die Idee der Reader-Monade. Als erstes stellt sich die Frage, was ist, wenn wir mehr Services oder andere Daten (etwa aus einer Property-Datei) brauchen. Deshalb bündeln wir das Ganze gleich in ein Config-Interface:

public interface Config {
    public UserService userService();
    //später mehr...
}

Dann fällt uns auf, dass alle Methoden den Typ Function<Config, Irgendwas> zurückgeben würden. Da sollten wir uns Schreibarbeit sparen, und diesem neuen Typ gleichzeitig ein paar nützliche Methoden (von denen zwei, nämlich pure und flatMap, das Ding auch formal zu einer Monade machen) verpassen:

//R wie "Reader"
public interface R<A> extends Function<Config, A> {

    @Override
    A apply(Config c);

    static <A> R<A>; pure(A a) {
        return s -> a;
    }

    default <B> R<B> map(Function<A, B> fn) {
        return s -> fn.apply(apply(s));
    }

    default <B> R<B> flatMap(Function<A, R<B>> fn) {
        return s -> fn.apply(apply(s)).apply(s);
    }
}

Damit würde unsere UserComponent so aussehen:

public class UserComponent {

    public R<User> getUser(long id) {
        return config -> config.userService().getUser(id);
    }

    public R<String> greet(User user) {
        return R.pure("Hello " + user.name + "!");
    }

    public R<List<User>> getAllUsers() {
        return config -> config.userService().findAll();
    }

    public R<String> greetAll() {
        return getAllUsers().map(list ->
                list.stream().map(user ->
                        "Hello " + user.name + "!\n").
                        reduce("", String::concat));
    }

}

OK, das sieht erst einmal ziemlich gewöhnungsbedürftig aus. getUser und getAllUsers sind einfach zu verstehen, sie reichen nur die Aufrufe an den Service weiter. Die Methode greet könnte eigentlich ohne Service auskommen, aber jeder weiß, wie schnell sich das ändern kann, und wer will sich schon merken, welche Methode jetzt eine Config braucht und welche nicht? Deshalb wird mit pure einfach ein R erzeugt, das einen Wert zurückliefert und dabei die Config völlig ignoriert. In greetAll sieht man, wie die Methoden aufeinander aufbauen können, in dem man sie mit map- (oder auch flatMap-) Aufrufen miteinander verknüppert. Interessant ist, dass hier überhaupt keine Spur mehr von einem Service oder einem Config-Objekt zu sehen ist, außer dem R-Rückgabetyp.

Wie wird das Ganze nun benutzt? Zuerst einmal braucht man natürlich eine Implementierung von Config. In unserem Mini-Beispiel reicht eine anonyme Klasse:

Config config = new Config() {
    @Override
    public UserService userService() {
        return new UserServiceImpl();
    }
};
...

Dann kann man Methoden wie gewohnt aufrufen, nur muss man überall ein .apply(config) dranhängen:

...
UserComponent userComp = new UserComponent();
System.out.println(userComp.greetAll().apply(config));
...

Natürlich können auch hier einzelne Methoden miteinander verknüpft werden:

...
System.out.println(userComp.getUser(42).
                   flatMap(userComp::greet).apply(config));
...

Das war das Grundprinzip der Reader-Monade als DI-Ersatz. Ich gebe zu, der entstehende Code sieht erst einmal ziemlich ungewöhnlich aus, und ich bin skeptisch, wie gut das Ganze in größeren Systemen funktionieren würde. Trotzdem ist es interessant zu sehen, wie man sich mit „Bordmitteln“ behelfen kann, wenn man kein DI-Framework einsetzen will.

Das böse M-Wort

Kann ich es wagen? Soll ich ich es wirklich aussprechen? Na gut, ich tu’s: Monaden! Nein, ganz im Ernst, ich verstehe das ganze Getue darum nicht. Ich denke, wenn ein Programmierer die Nützlichkeit von Monaden entdeckt hätte, und sie dann ihren Weg in die Kategorientheorie genommen hätten, wäre ihr „Image“ heute wesentlich besser. Nun war es andersherum, das rein theoretische Konstrukt hat sich in der Praxis als unglaublich nützlich erwiesen, aber so ganz bekommt es sein Image, theoretisch und komplex zu sein, nicht los. Es gibt viele gute Texte, die Monaden aus verschiedenen Blickwinkeln beleuchten. Ich will sie hier einmal ganz, ganz naiv in Scala implementieren, und am Ende wartet eine kleine Zugabe.

Viele Scala-Klassen verhalten sich wie Monaden. Typische Beispiele sind Option, Either und List. Ihnen ist gemeinsam, dass sie in der Lage sind, andere Objekte „einzupacken“ (einfach durch den Aufruf des Konstruktors), und sich in einem gewissen Sinne „transformieren“ zu lassen (z.B. über die map-Funktion). Diese beiden Operationen machen (zusammen mit drei Gesetzen, denen sie gehorchen müssen) eine Monade aus.

Während sich die „Transformations-Funktion“ am Typ selber festmachen läßt, klappt das mit der „Einpack-Funktion“ (oder Konstruktor) nicht ohne Weiteres. Natürlich könnte man jetzt dafür das Companion-Objekt einspannen, aber wir kopieren stattdessen Haskell, wo Monaden über Typklassen definiert werden. Hier ist unsere simples Monaden-Trait:

trait Monad[M[_]] {
    def pure[A](a: A): M[A]
    def bind[A, B](m: M[A], f: A => M[B]): M[B]
}

Dieses Trait ist über unseren Monaden-Typ M parametrisiert. M ist dabei ein Typ höherer Ordnung („higher kinded type“), der einen Typ-Parameter besitzen muss (deshalb M[_]). Die Methode pure übernimmt das „Einpacken“, und die Methode bind das Transformieren (in Haskell heißen die beiden Methoden übrigens „return“ und „>>=“). Schauen wir uns einmal zwei Beispiele an, wie dieses Trait implementiert werden könnte:

object OptionMonad extends Monad[Option] {
    //pure entsprechend Kommentar von Stefan W. verbessert. Danke!
    override def pure[A](a: A): Option[A] = if (a == null) None else Some(a) 
    override def bind[A,B](opt: Option[A], f: A => Option[B]): Option[B] = opt match {
      case Some(a) => f(a)
      case None => None
    }
}

object ListMonad extends Monad[List] {
    override def pure[A](a: A): List[A] = List(a)
    override def bind[A,B](list: List[A], f: A => List[B]): List[B] =
      (for(a <- list) yield f(a)).flatten
}

Das Einpacken ist einfach: OptionMonad.pure(a) konstruiert aus einem Wert a mittels Some(a) eine Option, List macht aus einem Wert eine einelementige Liste. Die Transformation sieht schlimmer aus, als sie in Wahrheit ist: Wie genau transformiert werden soll, wird über eine Transformationsfunktion f angegeben. In OptionMonad wird für ein Some(a) einfach diese übergebene Funktion ausgeführt (die ja wieder eine Option liefert), während None einfach ein None bleibt. Bei ListMonad wird die Funktion auf jedes Listenelement angewendet und zu einer neuen Liste zusammenfügt.

Die Methode bind sieht dem von Option und List gewohnten map sehr ähnlich, nur die Transformationsfunktion f sieht etwas anders aus. Können wir das hinbiegen? Aber sicher, wir schrieben einfach unsere eigene map-Methode. Allerdings brauchen wir ja auch noch die „passende“ Monaden-Implementierung. Dank impliziter Parameterübergabe ist das kein Problem:

object Test {

  implicit val om = OptionMonad
  implicit val lm = ListMonad

  def map[A,B,M[_]](m:M[A], f:A => B)(implicit monad:Monad[M]): M[B] =
     monad.bind[A,B](m, a => monad.pure(f(a)))
   
   ...
}

Wow, das ist schonmal starker Tobak. Aber eigentlich ganz logisch: Wir übergeben unseren Monaden-Typ und eine Funktion, die auch für ein „normales“ map geeignet wäre. Unsere Monaden-Implementierung lassen wir uns als einen impliziten Parameter übergeben (damit „simulieren“ wir gewissermaßen Typklassen wie in Haskell). Unsere „normale map-Funktion“ können wir für bind nicht verwenden, wir brauchen als Ergebnis ja den Monaden-Typ, nicht den transformierten Werte-Typ „B“. Deshalb müssen wir das Ergebnis von f(a) noch mittels pure verpacken. Okay, probieren wir unser selbstgestricktes map einmal aus:

object Test {

  ...
  
  def strlen(s: String): Int = s.length

  def main(args:Array[String]) {
     println(map(Option("cool"), strlen _))
     println(map(None:Option[String], strlen _))
     println(map(List[String](), strlen _))
     println(map(List("one", "two", "three"), strlen _))
  }
}

//--> Some(4)
//--> None
//--> List()
//--> List(3, 3, 5)

Wir wir sehen, funktioniert das gut, unsere Strings werden in ihre jeweilige Länge transformiert. Ein kleiner Haken ist, dass wir Some und None noch als Option kennzeichnen müssen, da sonst Scala nach einem impliziten Parameter Monad[Some] oder Monad[None] suchen würde. Alternativ könnte man natürlich auch map[String,Int,Option](…) schreiben. Für dieses Problem habe ich (trotz Nachfrage auf Stackoverflow) bisher keine Lösung finden können: Die Klasse <:< hilft nur dann weiter, wenn ein einziger impliziter Parameter sichtbar ist, und eine kontravariante Definition trait Monad[-Q[_]] ist nicht möglich, da sowohl pure als auch bind Werte zurückliefern – und Rückgabewerte können höchstens kovariant sein.

Aber das ist bis jetzt nicht viel Neues, schließlich können wir das bereits mit den "eingebauten" map-Methoden von Option und List. Deshalb eine kleine Zugabe: Was ist, wenn ich einen Monaden-Typ innerhalb eines Monaden-Typs habe, und transformieren will, also meinetwegen ein List[Option[String]] in eine List[Option[Int]]? Natürlich können wir das auch mit den "eingebauten" map-Methoden erledigen, aber trotzdem ist es ein gutes Beispiel, wie wir Monaden wie Legosteine kombinieren können, ohne deren konkrete Implementierung kennen zu müssen, und ohne dass sich die einzelnen "Ebenen" in die Quere kommen. Hier kommt also der Wahnsinn im Quadrat:

object Test {

  implicit val om = OptionMonad
  implicit val lm = ListMonad

  def innerMap[A,B,M[_],O[_]](o: O[M[A]], f: A => B)
                             (implicit monad: Monad[M], monadO: Monad[O]): O[M[B]] = {
    monadO.bind[M[A],M[B]](o, (m:M[A]) => monadO.pure{
      monad.bind[A,B](m, a => monad.pure(f(a)))
    })
  }

  def strlen(s: String): Int = s.length

  def main(args:Array[String]) {
     println(innerMap(Option(List("one", "two", "three")), strlen _))
     println(innerMap(List(Option("one"), Option("two"), None), strlen _))
     println(innerMap(List(List("one", "two"), List("three","four")), strlen _))
  }
}

//--> Some(List(3, 3, 5))
//--> List(Some(3), Some(3), None)
//--> List(List(3, 3), List(5, 4))

Ja, das sieht furchtbar aus, war auch etwas Gefrickel, bis ich es zum Laufen gebracht hatte, aber es funktionert einwandfrei.

Natürlich kratzt das alles nur an der Oberfläche, und Container sind nur eines von vielen möglichen Einsatzgebieten (wenn auch das anschaulichste). Eventuell ist euch aufgefallen, dass immer von "Einpacken", aber nie von "Auspacken" die Rede war. Und dafür gibt es auch keinen Weg, wenn der Typ das nicht selber ermöglicht (wie etwa Option.get). Das ist einer der Gründe, warum Haskell Monaden für veränderliche Zustände sowie Ein- und Ausgabe verwendet: Die "bösen" Seiteneffekte können aus einer Monade nicht "entkommen" (da Scala Seiteneffekte erlaubt, ist das natürlich für uns weniger interessant).

Wer mehr wissen will:

Eine „ordentliche“ Implementierung findet sich in Scalaz.

So, das wars schon, ich hoffe es hat nicht allzu weh getan.

Dann möchte ich nur noch auf die „What’s new in Scala 2.8“-Reihe auf www.scala-lang.org hinweisen (Liste in meiner Link-Seite).

Höhere Ordnung muss sein!

„Typen höherer Ordnung“ (Higher Order Types, Higher Kinded Types) oder „Typkonstruktoren“ (Type Constructors) klingt furchterregender, als es eigentlich ist, und zudem sind die Dinger richtig praktisch. Nun kommt an dieser Stelle meist der Hinweis auf Haskell, und wie nützlich selbige dort sind, etwa um Monaden und ähnliche Dinge zu implementieren. Das ist zwar richtig, schreckt aber eher ab, als das es weiterhilft. Nebenbei gesagt ist die ganze Monadenangelegenheit viel einfacher als man denkt, zumindest wenn man Tony Morris zuhört (Video und Präsentation) und nicht Leibnitz. Ich will allerdings an dieser Stelle abbiegen und diese komischen Typen an einem praktischen und ganz einfachen Beispiel vorstellen.

Vermutlich fast jeder von uns hat schon einmal die Aufgabe lösen dürfen, alle Permutationen einer Liste oder eines Strings zu bestimmen. Angenommen wir wollten für Scala ein kleines Tool zum Permutieren von Listen schreiben, dann sähe das zum Beispiel so aus:

object Permutation {
   def permutations[T](list: List[T]): Iterator[List[T]] = ... //eine tolle Implementierung
}

Und wenn wir ein Tool zum Permutieren von Arrays schreiben wollen, dann… Halt! Wollen wir wirklich für jede in Frage kommende Datenstruktur eine eigene Implementierung schreiben? Aber wie sollen wir von List, Array u.s.w. abstrahieren? Wir würden jetzt am liebsten schreiben „permutate[T, L[T]], wobei L irgend etwas listenartiges ist“. Der Witz ist, in Scala können wir genau das tun! Das L steht also für irgendeine Art von „Container“. Das einzige, was wir wissen müssen, ist wie wir Daten in den Container hinein- und wieder hinausbekommen. Tatsächlich reichen zwei Methoden:

  def grow(opt: Option[(L[T],T)]): L[T]
  def shrink(l: L[T]): Option[(L[T],T)]

Dabei erstellt grow(None) einen leeren Container, während grow(Some(container, value)) value in den container stopft und den „vergrößerten“ Container zurückgibt. shrink entfernt ein Element aus dem Container und gibt das Element und den „verkleinerten“ Container zurück, oder None, falls das nicht klappt, weil der Container leer ist. Nun haben wir alle Werkzeuge zusammen, um einen containertyp-unabhängiges Permutationstool zu schreiben:

trait Permutation[T,L[_]] {
  def grow(opt: Option[(L[T],T)]): L[T]
  def shrink(l: L[T]): Option[(L[T],T)]

  //Achtung, ineffiziente Implementierung!
  def permutations(l:L[T]):Iterator[L[T]] = {
    def it(list:List[T]):Iterator[List[T]] = list match {
      case Nil => Iterator.empty
      case h :: Nil => Iterator(List(h))
      case _ => (0 to (list.size-1)).map{n =>
          val(left,right) = list.splitAt(n)
          it(left ::: right.tail).map(l => right.head :: l)
        }.foldLeft(Iterator[List[T]]())((i1,i2) => i2 ++ i1)
    }
    def fromList(list:List[T]):L[T] = list match {
      case Nil => grow(None)
      case h :: t => grow(Some(fromList(t), h))
    }
    def toList(l: L[T]): List[T] = shrink(l) match {
      case None => List[T]()
      case Some((m,t)) => t :: toList(m)
    }
    it(toList(l)).map(fromList(_))
  }
}

Um den Typ höherer Ordnung zu definieren, benutzt man L[_], was soviel wie „Klasse, die einen Typparameter hat“ bedeutet. Um dieses Dingens dann konkret benutzen zu können, muss man natürlich einen passenden Parametertyp mitliefern, also z.B. L[T].

Mein Permutationscode ist alles andere als elegant und performant, aber es geht hier ums Prinzip: Egal was für einen Container wir geliefert bekommen, wir können seine Permutationen als Iterator liefern – vorausgesetzt, er behält die Einfügereihenfolge bei (ein HashSet wäre also eine schlechte Wahl). Natürlich müssen noch die beiden abstrakten Methoden grow und shrink implementiert werden, aber das ist ein Klacks verglichen mit dem Aufwand, jedesmal eine Permutations-Methode schreiben zu müssen.

Wie wendet man den Zauberkasten jetzt an? Nun, für Listen könnte man so etwas schreiben:

  case class ListPermutation[T] extends Permutation[T, List] {
    override def grow(opt: Option[(List[T],T)]): List[T] = opt match {
      case None => List[T]()
      case Some((l,t)) => t :: l
    }
    override def shrink(l: List[T]): Option[(List[T],T)] = l match {
      case Nil => None
      case h :: t => Some((t, h))
    }
  }

//Test
println(ListPermutation[Int].permutations(List(1,2,3)).toList)
//--> List(List(3, 2, 1), List(3, 1, 2), List(2, 3, 1), List(2, 1, 3), List(1, 3, 2), List(1, 2, 3))

Wie wäre es mit Array?

//Achtung, ineffiziente Implementierung!
  case class ArrayPermutation[T:ClassManifest] extends Permutation[T, Array] {
    override def grow(opt: Option[(Array[T],T)]): Array[T] = opt match {
      case None => Array[T]()
      case Some((l,t)) => (t :: l.toList).toArray
    }
    override def shrink(l: Array[T]): Option[(Array[T],T)] = l match {
      case Array() => None
      case array => val list = array.toList
        Some((list.tail.toArray, list.head))
    }
  }

//Test
println(ArrayPermutation[Char].permutations(Array('a','b','c')).toList.map(_.mkString))
//--> List(cba, cab, bca, bac, acb, abc)

Oder bedienen wir uns in java.util:

  import java.util.ArrayList
  case class ArrayListPermutation[T] extends Permutation[T, ArrayList] {
    override def grow(opt: Option[(ArrayList[T],T)]): ArrayList[T] = opt match {
      case None => new ArrayList[T]()
      case Some((l,t)) => l.add(t); l
    }
    override def shrink(l: ArrayList[T]): Option[(ArrayList[T],T)] =
      if (l.size == 0) None else {
        val t = l.remove(0)
        Some((l,t))
      }
  }

//Test
val al = new ArrayList[String]
al.add("x"); al.add("y"); al.add("z")
println(ArrayListPermutation[String].permutations(al).toList)
//--> List([x, y, z], [y, x, z], [x, z, y], [z, x, y], [y, z, x], [z, y, x])

Die Arbeit mit Typen höherer Ordnung ist gewöhnungsbedürftig: Man weiß eben kaum etwas über sie. An irgendeiner Stelle muss man deshalb „konkret“ werden, um nicht den Bodenkontakt zu verlieren (in unserem Fall die Methoden grow und shrink). Trotzdem ist diese Art der Abstraktion sehr nützlich, denn man kann auf sehr allgemeine Weise Operationen definieren, ohne die Schnittstelle der parametrisierten Typen genau zu kennen, was die ganze Konstruktion wahnsinnig flexibel macht. Monaden erlauben zum Beispiel, dass zwei Containertypen, die voneinander überhaupt nichts wissen, nach allen Regeln der Kunst verschachtelt oder umgepackt werden können. Und obwohl ich hier immer von „Containertypen“ spreche, weil das wohl am anschaulichsten ist, können natürlich auch andere Arten von parametrisierten Klassen genauso verallgemeinert werden, etwa „funktionsartige“ Klassen.

Scala 2.8 verwendet Typen höherer Ordnung in der renovierten Collection-Bibliothek. Eine Schwachstelle der alten Collections war, dass es an manchen Stellen kompliziert oder gar unmöglich war, den „richtigen“ Collection-Typ zurüchzuliefern. So war man sich nie sicher, ob ein Blub[A].map(A => B) auch ein Blub[B] zurücklieferte, oder vielleicht doch etwas Allgemeineres, etwa Seq[B]. Der Builder-Mechanismus in Scala 2.8 sorgt hinter den Kulissen dafür, dass man ziemlich sicher die Collection zurückbekommt, die man erwarten würde, und für diesen Trick sind Typen höherer Ordnung unverzichtbar.

Ich hoffe sehr, dass eure Gehirne jetzt im Zustand höherer Ordnung statt Konfusion sind. Aber grau ist alle Theorie, also probiert selbst einmal, was man mit den höheren Typen alles anstellen kann. Da man bisher hauptsächlich in Haskell (das z.B. keine Vererbung kennt) damit herumexperimentiert hat, kann ich mir nicht vorstellen, dass man bereits alle Anwendungsmöglichkeiten erforscht hat. Es winken also noch Entdeckerlorbeeren…