Teil 14: Generische Typen

Dieser Artikel ist eigentlich schon längst überfällig, doch musste ich ihn immer wieder zurückstellen, da andere Themen zuerst erklärt werden wollten. Generische Typen haben wir schon zu Genüge kennen gelernt, wir finden sie z.B. bei Collections:

scala> List[Int](1, 2, 3)
res0: List[Int] = List(1, 2, 3)

scala> List[String]("foo", "bar")
res1: List[String] = List(foo, bar)

In diesem Fall wird auch von einem parametrisierten Typ gesprochen. Ein parametrisierter Typ kann ein Typ sein über den man zur Zeit der Codeentwicklung noch nicht Bescheid weiß. Er kann beliebige Typen repräsentieren und ermöglicht uns wiederverwendbaren Code zu schreiben. In obigem Beispiel können wir unsere Liste z.B. mit Ints oder mit Strings kreieren. Der Typparameter wird in Scala durch eckige Klammern repräsentiert und steht immer vor runden oder geschweiften Klammern. Nach dem Typparameter kann z.B. ein Konstruktoraufruf, eine Parameterliste oder eine Blockdefinition kommen. Dank Scalas Typinferenz müssen wir die Typparameter unserer Objekte jedoch nur selten notieren. Typen, die einen oder mehrere Typparameter besitzen, werden auch als generische Typen bezeichnet. Wie an obigem Codebeispiel zu erkennen gibt uns die REPL die Typparameter nur am statischen Typ, nicht jedoch am Runtime-Typ aus. Das liegt daran, dass Scala der „type erasure“ der JVM unterliegt, die besagt, dass alle Informationen zu Typparametern zur Laufzeit nicht mehr vorhanden sind. Die JVM ersetzt alle Typparameter durch Object, dem Typ, dem alle Objekte auf der JVM unterliegen. Zur Laufzeit ist eine List[Int] also identisch mit einer List[String], da sie beide nur noch als List[Object] repräsentiert werden. Wirklich stören tut die „type erasure“ der JVM aber selten, da der Scala-Compiler dafür sorgt, dass wir überall auch die richtigen Typen einsetzen. Natürlich gibt es auch Anwendungsfälle, bei denen es schön wäre, wenn die Typinformationen zur Laufzeit vorhanden wäre. Scala stellt uns hierfür aber ein paar „Tricks“ zur Verfügung, mit denen wir uns in einem solchen Fall weiterhelfen können, aber dazu später mehr.

Fangen wir damit an unseren eigenen Code mit Typparametern zu schreiben.

def size[A](xs: List[A]): Int = {
  def loop(xs: List[A], i: Int): Int =
    if (xs.isEmpty) i else loop(xs.tail, i+1)
  loop(xs, 0)
}

Bisher haben wir unseren Code meistens auf Basis von List[Int] geschrieben. Mit obigem Code ändert sich das. Die Methode erwartet nun eine List[A]. A steht als Platzhalter für irgendeinen Typ, der uns jetzt noch nicht bekannt ist. Da es den Typ A aber noch nicht gibt müssen wir ihn irgendwo definieren – in Scala tun wir dies indem wir ihn in eckigen Klammern nach dem Methodennamen schreiben. Damit erzeugen wir für den Gültigkeitsbereich der Methode eben jenen Typparameter und können ihn fortan verwenden. Wir müssen im Folgenden nur dafür Sorge tragen, dass wir den definierten Typ überall dort verwenden wo wir ansonsten einen konkreten Typ (wie Int oder String) notiert hätten. Haben wir alles richtig gemacht, sollte unser Code für jegliche Listen funktionieren:

scala> size(List(1,2,3))
res0: Int = 3

scala> size(List('a','b'))
res1: Int = 2

Der Compiler sucht für uns alle Vorkommnisse von A heraus und füllt die benötigten Typen ein. Das macht sich dann bemerkbar wenn wir einen generischen Rückgabetyp definieren:

def reverse[A](xs: List[A]): List[A] = {
  def loop(xs: List[A], ys: List[A]): List[A] =
    if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
  loop(xs, Nil)
}

scala> reverse(List(1, 2, 3))
res4: List[Int] = List(3, 2, 1)

scala> reverse(List("a", "b", "c"))
res5: List[java.lang.String] = List(c, b, a)

Wie unschwer zu erkennen, besitzt die zurückgegebene Liste immer den richtigen Typparameter. Der Name des Typparameters ist im Übrigen frei wählbar. Eingebürgert hat sich aber, dass ein ein einzelner großer Buchstabe verwendet wird, beginnend mit A. Je nach dem in welchem Kontext der Typ benutzt wird, sieht man auch oft mehrere Zeichen umfassende Symbole, wie CC für Collection oder Ret für einen Rückgabetyp. Wollen wir mehr als einen Typparameter haben, so müssen wir diese durch ein Komma trennen:

def print[A, B](a: A, b: B) {
  println(a)
  println(b)
}

scala> print(5, "hello")
5
hello

Nach der gleichen Vorgehensweise wie bei Methoden können wir auch Klassen mit Typparametern versehen:

scala> case class Box[A](a: A)
defined class Box

scala> Box(3)
res0: Box[Int] = Box(3)

scala> Box("Hello")
res1: Box[java.lang.String] = Box(Hello)

Type bounds

Manchmal wollen wir aber keinen Code für beliebige Typen schreiben, sondern Code für Typen mit einer bestimmten Eigenschaft. Die Frage ist jetzt nur was eine solche Eigenschaft sein könnte. Wie wäre es wenn wir die Objekte eines Typs miteinander vergleichen könnten? Der Compiler ist so freundlich und implementiert uns für Fallklassen die equals-Methode:

scala> Box(3) == Box(3)
res4: Boolean = true

scala> Box(3) == Box(7)
res5: Boolean = false

Bei den größer- und kleiner-Methoden sieht es da schon schlechter aus:

scala> Box(3) < Box(9)
<console>:10: error: value < is not a member of Box[Int]
              Box(3) < Box(9)
                     ^

scala> Box(3) > Box(9)
<console>:10: error: value > is not a member of Box[Int]
              Box(3) > Box(9)
                     ^

Das ist auch der Grund weshalb sich die Objekte nicht sortieren lassen, da sie einfach keine Wertigkeit besitzen:

scala> import collection.immutable._
import collection.immutable._

scala> SortedSet(Box(3), Box(9))
:13: error: No implicit Ordering defined for Box[Int].
              SortedSet(Box(3), Box(9))
                       ^

Die Fehlermeldung des Compilers gibt uns den Hinweis, dass wir eine Sortierungsmöglichkeit noch einbauen müssen. In Scala sieht die Standardvorgehensweise dafür so aus, dass die zu sortierende Klasse den Typ „Ordered“ implementieren müssen:

scala> case class IntBox(i: Int) extends Ordered[IntBox]
:12: error: class IntBox needs to be abstract, since method compare in trait Ordered of type (that: IntBox)Int is not defined
       case class IntBox(i: Int) extends Ordered[IntBox]
                  ^

Ordering definiert eine Methode namens „compare“, die wir noch implementieren müssen:

case class IntBox(i: Int) extends Ordered[IntBox] {
  def compare(x: IntBox) =
    this.i-x.i
}

scala> SortedSet(IntBox(3), IntBox(9), IntBox(1))
res18: scala.collection.immutable.SortedSet[IntBox] = TreeSet(IntBox(1), IntBox(3), IntBox(9))

scala> IntBox(7) < IntBox(3) res19: Boolean = false scala> IntBox(7) > IntBox(3)
res20: Boolean = true

scala> IntBox(3) >= IntBox(3)
res21: Boolean = true

Das Verhalten ist genau so wie wir es erwarten. Ordered definiert alle Vergleichsmethoden, die es in Scala gibt. Wir müssen uns nur noch darum kümmern, dass die Vergleichsmethoden auch richtig arbeiten was durch durch die Implementierung der compare-Methode sicher stellen können. Die Parametrisierung von Ordered bestimmt den Typ des Parameters den die compare-Methode erwartet. Wer wissen möchte wie Ordered genau funktioniert, kann in dessen Sourcen gucken.

Euch dürfte aufgefallen sein, dass ich im letzten Beispiel keine parametrisierte Box benutzt habe. Ich hätte es gerne getan, nur leider besitzt ein generischer Typ keine Subtraktionsmethode, mit deren Hilfe wir die Wertigkeit des Objekts errechnen könnten. In Scala gibt es einen weiteren Type namens „Ordering“, der es uns erlaubt eine Wertigkeit auch für parametrisierte Typen anzugeben. Um Ordering korrekt benutzen zu können benötigt ihr aber noch ein wenig mehr Wissen über Scalas implizite Typen. Da das aber Stoff für ein weiteres Kapitel ist, werden wir uns hier nicht weiter mit Ordering befassen. Die einzigen, die wir auf einen parametrisierten Typ aufrufen können, sind die, die wir auch auf den Typ Object aufrufen können. Es besteht also die Möglichkeit, dass wir den Hash-Code miteinander vergleichen:

case class Box[A](a: A) extends Ordered[A] {
  def compare(a: A) =
    this.hashCode-a.hashCode
}

Diese Lösung erfordert aber eine korrekt implementierte hashCode-Methode und sollte daher nicht immer das erste Mittel der Wahl sein.

Kommen wir lieber wieder zu den Eigenschaften zurück, die wir den parametrisierten Typen mitgeben wollen:

class Sorter[A <: Ordered[A]]

Das <:-Symbol bedeutet, dass A ein Untertyp von Ordered[A] sein muss. Versuchen wir fortan eine Instanz vor Sorter mit einem Parameter zu erzeugen, der nicht sortiert werden kann, erhalten wir eine Fehlermeldung:

scala> new Sorter[IntBox]
res17: Sorter[IntBox] = Sorter@3eadff2f

scala> val x = new Sorter[Boolean]
<console>:8: error: type arguments [Boolean] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Boolean]
           ^
<console>:8: error: type arguments [Boolean] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Boolean]
                   ^

scala> val x = new Sorter[Int]
<console>:8: error: type arguments [Int] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Int]
           ^
<console>:8: error: type arguments [Int] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Int]
                   ^

Int besitzt definitiv Vergleichsmethoden, implementiert aber nicht den Typ Ordered, weshalb unser Code auch nicht kompiliert. Tatsächlich haben wir mit Ordered ein paar Krücken gewählt, die eher für Notsituation zu gebrauchen sind. Was wir wirklich brauchen ist nicht Ordered, sondern Ordering, das wir ja aber noch nicht verwenden können. Ok ok, ich bin nachsichtig und strecke euch den benötigten Code vor, gebe aber keine Garantie darauf, dass ihr ihn auch versteht.

class Sorter[A](implicit ord: Ordering[A])

case class Box[A](a: A)
object Box {
  implicit def ord[A]: Ordering[Box[A]] =
    new Ordering[Box[A]] {
      def compare(x: Box[A], y: Box[A]) =
        y.a.hashCode-x.a.hashCode
    }
}

Der implizite Parameter stellt sicher, dass eine Sorter-Instanz auch nur für Typen erstellt werden kann, die über eine geeignete Vergleichsmöglichkeit verfügen. Wir können den Code nun erfolgreich nutzen:

scala> new Sorter[Box[Int]]
res0: Sorter[Box[Int]] = Sorter@32a88bc2

scala> new Sorter[Int]
res1: Sorter[Int] = Sorter@5e3b8219

scala> new Sorter[Boolean]
res2: Sorter[Boolean] = Sorter@37f2ae62

scala> class X
defined class X

scala> new Sorter[X]
:10: error: No implicit Ordering defined for X.
              new Sorter[X]
              ^

Falls ihr das Beispiel oben ausprobiert dabei aber nicht das gleiche Ergebnis erhaltet habt müsst ihr die implizite Methode noch importieren (je nach dem wo und wie ihr den Code definiert hab wird er automatisch vom Compiler gefunden):

import Box._

Überraschen sollte euch hier, dass der Code auch für Int und Boolean funktioniert. Weshalb er es tut will ich hier aber nicht näher erläutern – dafür müsst ihr euch noch bis zu einem der nächsten Kapitel gedulden.

Wir können einen Typparameter auch nach oben hin beschränken:

class Bar
class Baz extends Bar
class Buz extends Baz
class Boz extends Buz

class Foo[A >: Buz]

Dies führt dazu, dass nur Obertypen von Buz erlaubt sind, bei allen anderen bekommen wir eine Fehlermeldung:

scala> new Foo[Bar]
res8: Foo[Bar] = Foo@4e7f3159

scala> new Foo[Baz]
res9: Foo[Baz] = Foo@caa6635

scala> new Foo[Buz]
res10: Foo[Buz] = Foo@48b91881

scala> new Foo[Boz]
:12: error: type arguments [Boz] do not conform to class Foo's type parameter bounds [A >: Buz]
       val res11 =
           ^
:13: error: type arguments [Boz] do not conform to class Foo's type parameter bounds [A >: Buz]
              new Foo[Boz]
                  ^

Es ist sogar möglich beide Beschränkungen miteinander zu kombinieren:

class Foo[A >: Bar <: Baz]

Hier darf Foo nur mit Obertypen von Bar instanziiert werden, die gleichzeitig auch Untertypen von Baz sind.

Abstrakte Typen

Neben parametrisierten Typen bietet Scala auch sogenannte abstrakte Typen, die eine weitere Möglichkeit darstellen wie man generisch programmieren kann.

abstract class Box {
  type A
  val value: A
}

scala> new Box { type A = Int; val value = 13 }
res0: Box{type A = Int} = $anon$1@61735602

scala> new Box { type A = String; val value = "hello" }
res1: Box{type A = String} = $anon$1@20dbd794

Zur Deklaration eines abstrakten Typs wird das type-Schlüsselwort verwendet, das wir auch zum späteren Binden eines konkreten Typs benötigen.

Genau wie die parametrisierten Typen können auch die abstrakten Typen mit Beschränkungen versehen werden:

type A <: B
type A >: B
type A >: B <: C

Die semantische Bedeutung der Symbole habe ich weiter oben schon erklärt und kann dort nachgeschlagen werden falls ihr sie noch nicht verinnerlicht haben solltet.

Kleine Bemerkung am Rande: ein gebundener abstrakter Typ ist immer ein Untertyp des jeweiligen deklarierten Typs. Es gilt also:

C { type A = SomeType } <: C

Abstrakte Typen unterscheiden sich auf den ersten Blick nicht sonderlich von parametrisierten Typen. Tatsächlich wird man in den meisten Fällen die parametrisierten Typen auch bevorzugen, da sie nicht so langatmig zu notieren sind und sie dank Typinferenz oft auch gar nicht erst notiert werden müssen. Der große Vorteil von abstrakten Typen ist, dass sie vererbt werden können und somit typisierte Ableitungen erlauben.

trait Suite {
  type A
}
trait StringBuilderSuite extends Suite {
  type A = StringBuilder
}
class DefSuite extends Suite with StringBuilderSuite

Dieser Code bietet zuerst einmal etwas Neues: Traits. Was sie genau machen und wie sie sich von Klassen unterscheiden möchte ich euch im nächsten Kapitel beschreiben. Für den Rest dieses Kapitels reicht es zu wissen, dass man mit ihnen (und mit dem with-Schlüsselwort) eine Art Mehrfachvererbung erzeugen kann und dass sie abstrakte Typen sind und deshalb nicht so ohne weiteres instanziiert werden können:

scala> new Suite
<console>:9: error: trait Suite is abstract; cannot be instantiated
              new Suite
              ^

In obigem Code haben wir uns die Vererbung der abstrakten Typen zu Nutze gemacht und uns so ein wenig Schreibarbeit erspart. Wenn wir parametrisierte Typen benutzen fällt der Unterschied sofort auf:

trait Suite[A]
trait StringBuilderSuite extends Suite[StringBuilder]
class DefSuite extends Suite[StringBuilder] with StringBuilderSuite

Die Klasse DefSuite muss nun zwangsläufig noch einmal parametrisiert werden, obwohl die Parametrisierung schon im Trait StringBuilderSuite festgelegt wurde. Ohne die erneute Parametrisierung würde der Code nicht kompilieren:

scala> class DefSuite extends Suite with StringBuilderSuite
<console>:9: error: trait Suite takes type parameters
       class DefSuite extends Suite with StringBuilderSuite
                              ^

Abstrakte Typen bieten keine großen Vorteile gegenüber den Parametrisierten, runden Scalas Typsystem aber noch ein wenig ab – einen Anwendungsfall für sie kann man immer mal wieder finden.

Scalas generische Typen bieten noch ein paar Feinheiten, die ich hier noch nicht genannt habe und auch nicht mehr nennen möchte. Manches werde ich – wenn es angebracht ist – im weiteren Verlauf des Tutorials irgendwo einpflegen, manch anderem – wie z.B. Varianzen – gebe ich noch ein eigenes Kapitel, damit sie in der Menge von Scalas Möglichkeiten nicht untergehen.

Advertisements

2 comments so far

  1. Dominik on

    Finde ich super, dass hier regelmaessig gepostet wird.

    • antoras on

      Mehr oder weniger regelmäßig. Hab in letzter Zeit studienbedingt viel zu tun, aber bald sind wieder Semesterferien, dann kann ich wieder mehr Zeit aufbringen…


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

%d Bloggern gefällt das: