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).

Advertisements

7 Gedanken zu “Das böse M-Wort

  1. Deine Definition von ListMonad.bind sieht so aus:

    (for(a <- list) yield f(a).head).toList

    Warum das head und nicht einfach flatMap?

  2. Aus „didaktischen Gründen“. Normalerweise würde man einfach list.flatMap(f) schreiben, aber damit hätte ich bind mit einer Variante von bind „erklärt“. Deshalb ich wollte in den Rückgabewert lieber in einer Weise „per Hand“ konstruieren, die sich Schritt für Schritt nachvollziehen läßt, statt einfach die „Black-Box“ flatMap zu benutzen. Aber vielleicht war das ein wenig *zu* hintersinnig…

  3. > Schauen wir uns einmal zwei Beispiele an, wie dieses Trait implementiert werden könnte:

    Müsste hier nicht auch bei ‚pure‘ None berücksichtigt werden?

    object OptionMonad extends Monad[Option] {
    	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
    	}
    }
    

    Den Links möchte ich jedenfalls 2 dazugesellen – einen für die Freunde des Videos eine Art Antwort auf die These, Monaden seien Elephanten, nämlich Monaden seien Kisten voller Bananen 🙂 http://vimeo.com/8729673 von Tony Morris, und von der gleichen Personen eine Sammlung Übungen auf seinem Blog, http://blog.tmorris.net/monad-exercises-in-scala/ die mir ganz schön Kopfzerbrechen machen.

  4. Was ich als Korrektur vorgeschlagen habe (die Aufnahme der Möglichkeit ‚None‘) macht besagter Herr Morris jedoch ganz genauso, wie mir jetzt eine erneute Beschäftigung damit gezeigt hat.

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