Polymorphismus
In diesem Kapitel wird das Konzept des parametrischen Polymorphismus vorgestellt. Dieses Konzept wird in anderen Programmiersprachen wie Java und C# auch als Generics bezeichnet. Neben dem parametrischen Polymorphismus gibt es noch andere Formen von Polymorphismus, etwa Adhoc-Polymorphismus (Überladung). Im Kontext einer funktionalen Programmiersprache meint man mit dem Begriff Polymorphismus meistens parametrischen Polymorphismus.
Wie in Programmiersprachen wie Java und C# kann man in Elm Datentypen definieren, die generisch über dem Typ der Elemente sind. Tatsächlich haben Programmiersprachen wie Java und C# dieses Konzept von den funktionalen Programmiersprachen übernommen. Die Idee des parametrischen Polymorphismus1 wurde vor 50 Jahren für die funktionale Programmiersprache ML entwickelt. Es hat dann zum Beispiel 30 Jahre gedauert, bis Java dieses Konzept erhalten hat. In diesem Kapitel wollen wir uns anschauen, wie das Konzept des parametrischen Polymorphismus in Elm umgesetzt ist.
Einfache polymorphe Datentypen
Häufig möchte man einen Datentyp nicht nur mit einem konkreten Typ verwenden, sondern für verschiedene Typen.
Ein Beispiel für einen solchen Datentyp ist der Datentyp Maybe.
Dieser Datentyp wird genutzt, um anzuzeigen, dass eine Funktion möglicherweise kein Ergebnis liefert und stellt damit eine Art Ersatz der Null-Referenz dar, die in objekt-orientierten Sprachen für diesen Zweck genutzt wird.
Der Typ Maybe ist wie folgt definiert.
type Maybe a
= Just a
| Nothing
Maybe nimmt ein Argument, das a heißt, und auch als Typparameter oder Typvariable bezeichnet wird.
Typvariablen starten in Elm im Gegensatz zu Typen mit einem kleinen Buchstaben.
Wenn wir den Datentyp Maybe verwenden, müssen wir für den Typparameter einen konkreten Typ angeben.
Ein Datentyp wie Maybe, der noch Typen als Argumente erhält, wird als polymorpher Typ oder auch als Typkonstruktor bezeichnet.
Im Gegensatz zu polymorphen Typen werden Datentypen, die wir zuvor kennengelernt haben, als monomorphe Typen bezeichnet.
Die folgenden Beispiele definieren Werte von Maybe-Typen.
exampleMaybe1 : Maybe Int
exampleMaybe1 =
Just 3
exampleMaybe2 : Maybe Int
exampleMaybe2 =
Nothing
exampleMaybe3 : Maybe String
exampleMaybe3 =
Nothing
exampleMaybe4 : Maybe String
exampleMaybe4 =
Just "a"
Als erstes einfaches Beispiel wollen wir die Funktion
toInt : String -> Maybe Int
aus dem Modul String betrachten.
Falls das Argument der Funktion toInt keine ganze Zahl repräsentiert, liefert die Funktion den Wert Nothing.
Andernfalls erhalten wir ein Just, das den Integer enthält, der aus dem String erzeugt wurde.
Wir können zum Beispiel die folgende Funktion definieren, die eine Benutzereingabe für einen Monat überprüft.
module Month exposing (Month(..), parse, fromInt)
type Month
= Jan
| Feb
| Mar
| Apr
| May
| Jun
| Jul
| Aug
| Sep
| Oct
| Nov
| Dec
parse : String -> Maybe Month
parse userInput =
case String.toInt userInput of
Just n ->
fromInt n
Nothing ->
Nothing
fromInt : Int -> Maybe Month
fromInt int =
case int of
1 ->
Just Jan
2 ->
Just Feb
3 ->
Just Mar
4 ->
Just Apr
5 ->
Just May
6 ->
Just Jun
7 ->
Just Jul
8 ->
Just Aug
9 ->
Just Sep
10 ->
Just Oct
11 ->
Just Nov
12 ->
Just Dec
_ ->
Nothing
Der Aufruf parse "a" liefert Nothing, da "a" durch die Funktion String.toInt nicht in einen Int umgewandelt werden kann.
Der Aufruf parse "-1" liefert Nothing, da "-1" zwar eine Zahl darstellt, die Zahl aber nicht zwischen 1 und 12 liegt.
Der Aufruf parse "1" liefert schließlich als Ergebnis Just Jan.
Viele andere Programmiersprachen stellen einen Datentyp wie Maybe ebenfalls zur Verfügung.
So gibt es in Java zum Beispiel die Klasse java.util.Optional, die ebenfalls einen Typparameter nimmt und für die gleichen Zweck gedacht ist.
Ein elementarer Unterschied in Programmiersprachen wie Java ist aber, dass es trotzdem noch den Wert null gibt.
Das heißt, man muss eigentlich an jeder Stelle weiterhin auf null prüfen, da es keine Garantie gibt, dass der Typ Optional an allen Stellen als Null-Ersatz genutzt wird.
In Programmiersprachen wie Elm und Haskell existiert aber gar keine Null-Referenz.
Das heißt, wenn eine Funktion möglicherweise kein Ergebnis zurückliefert, liefert die Funktion einen Wert vom Typ Maybe.
Daher wissen wir durch das Typsystem, an welchen Stellen eine Art von Null-Referenz auftreten kann.
Null-Referenzen sind in der Programmierung ein Problem, da sie für viele Laufzeitfehler und damit für Schaden in der Industrie sorgen.
Der Erfinder der Null-Referenz, Tony Hoare2, bezeichnet die Erfindung der Null-Referenz als seinen Milliarden-Dollar-Fehler3, da Null-Referenzen die Industrie vermutlich bereits mehrere Milliarden Dollar gekostet haben.
Wenn man in einer Anwendung einen Fehlerfall modelliert, möchte man häufig noch einen Grund für das Fehlschlagen der Operation zur Verfügung stellen.
Für diesen Zweck wird der Datentyp Result genutzt.
Der Datentyp Result ist dabei wie folgt definiert.
type Result error value
= Ok value
| Err error
Der Typkonstruktor Result erhält zwei Typparameter.
Der erste Typparameter ist dabei der Typ, der im Konstruktor Err gespeichert wird.
Der zweite Typparameter ist der Typ, der im Konstruktor Ok gespeichert wird.
Wir wollen den Datentyp Result nutzen, um in der Funktion parse einen Grund zu liefern, warum die Konvertierung fehlgeschlagen ist.
Hierbei bedeutet der Typ Result String Month, dass wir im Erfolgsfall den Konstruktor Ok erhalten und sein Argument den Typ Month hat.
Im Fehlerfall erhalten wir den Konstruktor Err und sein Argument ist vom Typ String.
parse : String -> Result String Month
parse userInput =
case String.toInt userInput of
Just int ->
fromInt int
Nothing ->
Err ("Fehler beim Parsen von \"" ++ userInput ++ "\" als Int")
fromInt : Int -> Result String Month
fromInt int =
case int of
1 ->
Ok Jan
2 ->
Ok Feb
3 ->
Ok Mar
4 ->
Ok Apr
5 ->
Ok May
6 ->
Ok Jun
7 ->
Ok Jul
8 ->
Ok Aug
9 ->
Ok Sep
10 ->
Ok Oct
11 ->
Ok Nov
12 ->
Ok Dec
_ ->
Err ("Invalider Monat " ++ String.fromInt month)
Der Aufruf parse "a" liefert in dieser Implementierung Err "Error parsing \"a\" as Int".
Das heißt, wir erhalten nicht nur die Information, dass die Verarbeitung fehlgeschlagen ist, sondern auch, warum die Verarbeitung fehlgeschlagen ist.
Wir verwenden an dieser Stelle zur Vereinfachung einen Wert vom Typ String für die Fehlermeldung.
In einer Anwendung sollte man für die Modellierung von Fehlern immer auf einen strukturierten Datentyp wie den folgenden zurückgreifen.
Andernfalls ist es zum Beispiel nicht sinnvoll möglich, eine Fallunterscheidung über den Fehler durchzuführen, der aufgetreten ist.
Wenn wir den Datentyp String für Fehler verwenden, ist es auch nicht möglich, die Fehler zu internationalisieren, also in verschiedene Sprachen zu übersetzen.
In unserem Beispiel können wir den folgenden Datentyp für mögliche Fehlermeldungen verwenden. Wenn wir diesen Datentyp für den Typ der Fehler verwenden, können wir diese beiden Probleme vermeiden.
type Error
= ParseError String
| InvalidMonth Int
Der ParseError beschreibt, dass der String, den wir eingelesen haben, bereits keine Zahl repräsentiert und der Konstruktor InvalidMonth beschreibt, dass die Zahl kein valider Monat war.
Um die Fehlermeldung dem Nutzer später anzeigen zu können, definieren wir eine Funktion, welche einen Error in eine lesbare Fehlermeldung umwandelt.
toText : Error -> String
toText error =
case error of
ParseError userInput ->
"Fehler beim Parsen von \"" ++ userInput ++ "\" als Int"
InvalidMonth month ->
"Invalider Monat " ++ String.fromInt month
Da der Datentyp Result polymorph im Typ des Fehlers ist, können wir den Datentyp Result auch mit unserem Datentyp Error verwenden.
parse : String -> Result Error Month
parse userInput =
case String.toInt userInput of
Just int ->
fromInt int
Nothing ->
Err (ParseError userInput)
fromInt : Int -> Result String Month
fromInt int =
case int of
1 ->
Ok Jan
2 ->
Ok Feb
3 ->
Ok Mar
4 ->
Ok Apr
5 ->
Ok May
6 ->
Ok Jun
7 ->
Ok Jul
8 ->
Ok Aug
9 ->
Ok Sep
10 ->
Ok Oct
11 ->
Ok Nov
12 ->
Ok Dec
_ ->
Err (InvalidMonth month)
Der Aufruf parse "a" liefert in dieser Implementierung Err (ParseError "a").
Rekursive polymorphe Datentypen
Auch rekursive algebraische Datentypen können polymorph sein. Insbesondere der weitverbreitete Listen-Datentyp wird in funktionalen Sprachen polymorph definiert. Der folgende Datentyp definiert einen polymorphen Listendatentyp.
type PolyList a
= Nil
| Cons a (PolyList a)
Hierbei ist vor allem zu beachten, dass wir auch bei der rekursiven Verwendung den Typparameter a übergeben müssen, da PolyList ein Typkonstruktor ist und somit ein Argument verlangt.
Daher liefert eine Definition der Form Cons a PolyList einen Compiler-Fehler, da PolyList immer ein Argument erhalten muss.
Durch PolyList a im Argument von Cons geben wir an , dass der Rest der Liste Elemente vom gleichen Typ wie die bisherige Liste enthält.
Wir können wie folgt Werte von verschiedenen Instanzen des Typkonstruktors PolyList definieren.
exampleConsList1 : PolyList Int
exampleConsList1 =
Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))
exampleConsList2 : PolyList String
exampleConsList2 =
Cons "a" (Cons "z" (Cons "y" Nil))
exampleConsList3 : PolyList Bool
exampleConsList3 =
Cons False (Cons True (Cons True (Cons False Nil)))
Der Listendatentyp ist in Elm genau definiert wie der Datentyp PolyList, verwendet aber eine spezielle Syntax.
Die folgende Definition liefert in Elm einen Syntaxfehler, illustriert aber den Listendatentyp, wie er in Elm definiert ist.
type List a
= []
| a :: List a
Das heißt, der Konstruktor für die leere Liste verwendet in Elm nicht den Namen Nil sondern die Zeichenfolge [].
Der Konstruktor, um ein Element vorne an eine Liste anzuhängen, heißt außerdem nicht Cons, sondern :: und wird infix verwendet.
Das heißt, der Konstruktor :: wird zwischen seine Argumente geschrieben.
Alle anderen Konstruktoren werden vor ihre Argumente geschrieben.
Bei Funktionen kennen wir auch beide Varianten, so wird eine selbstdefinierte Funktion vor ihre Argumente geschrieben, also zum Beispiel f 1 2.
Die Funktion für die Addition wird aber zum Beispiel auch infix verwendet, also zum Beispiel 1 + 2.
Mithilfe des vordefinierten Listendatentyps können wir wie folgt eine Liste definieren.
exampleList1 : List Int
exampleList1 =
1 :: (2 :: (3 :: (4 :: [])))
Der Operator :: ist rechts-assoziativ.
Wir können die Klammern bei der Definition einer Liste also auch weglassen, wie im folgenden Beispiel.
exampleList2 : List String
exampleList2 =
"a" :: "z" :: "y" :: []
Der Typ, den wir an den Typkonstruktor List übergeben, kann wiederum ein komplexer Typ sein.
Das heißt, wir können zum Beispiel wie folgt eine Liste von Maybe-Werten definieren.
exampleList3 : List (Maybe Int)
exampleList3 =
Nothing :: Just 23 :: Just 42 :: []
Wir haben in der Einleitung bereits eine Kurzschreibweise für konkrete Listen kennengelernt. Diese Kurzschreibweise stellt nur syntaktischen Zucker4 für die obige Schreibweise dar. Daher kann man diese Kurzschreibweise auch in Pattern verwenden. Die folgende Definition nutzt diese Kurzschreibweise für Listen einer festen Länge.
exampleList4 : List Bool
exampleList4 =
[ False, True, False ]
Der Ausdruck [ False, True, False ] ist zum Beispiel syntaktischer Zucker für den Ausdruck False :: True :: False :: [].
-
A Logic for Computable Functions with reflexive and polymorphic types - Milner, R., Morris, L., Newey, M. (1975) ↩
-
Sir Charles Antony Richard (Tony) Hoare ist einer der bedeutendsten Informatiker der früheren Jahre der Informatik. ↩
-
Vortrag “Null References: The Billion Dollar Mistake” aus dem Jahr 2009 von Tony Hoare. ↩
-
Der Begriff syntaktischer Zucker geht ebenfalls auf Peter J. Landin zurück. ↩