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…

Advertisements

2 Gedanken zu “Höhere Ordnung muss sein!

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