Typklasse (Informatik)
Typklassen sind ein Konstrukt der funktionalen Programmierung zur Implementierung von Ad-hoc-Polymorphie. Typklassen wurden für die Sprache Haskell entwickelt. Sie ähneln vom Prinzip her dem Konzept der Schnittstellen, haben aber nichts mit den Klassen der objektorientierten Programmierung zu tun.
Geschichte
Typklassen wurden ursprünglich entwickelt, um auf systematische Weise mathematische Operatoren zu überladen.[1] Der Ansatz erwies sich als sehr vielseitig, sodass man ihn schnell auch für andere Dinge, wie z. B. Monaden verwendete. Heutzutage sind Typklassen eines der wichtigsten Werkzeuge der Sprache Haskell und finden in fast allen Bereichen Anwendung, meist zur Definition von Schnittstellen oder Generalisierung von Bibliotheken.
Einführung
Typklassen definieren Funktionen, die für jede Instanz der Typklasse aufgerufen werden können. Man kann eine Instanz für jeden Typ erstellen, indem man die Funktionen der Typklasse für den jeweiligen Typ definiert. Ein einfaches Beispiel ist der Operator (==), der zwei Variablen auf Gleichheit überprüft. (In Haskell sind Operatoren das gleiche wie Funktionen und werden nicht gesondert behandelt, allerdings werden sie in Infixnotation verwendet) Die zugehörige Typklasse Eq (von engl. equality) ist folgendermaßen definiert:
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
a == b = not (a /= b)
a /= b = not (a == b)
Die Klasse definiert zwei Funktionen, die jeweils zwei Variablen vom Typ a, dem Parameter der Typklasse, als Argumente haben: (==) ist ein Operator, der zwei Variablen auf Gleichheit überprüft, der Operator (/=) prüft auf Ungleichheit. Sein Symbol ist vom mathematischen Zeichen abgeleitet. Neben der Definition der Operatoren (Zeilen 2 und 3), bei der ihr Typ angegeben wird, kann man auch eine Standardimplementation der Operatoren angeben. Dies ist z. B. dann nützlich, wenn einige Funktionen potentiell redundant sind, aber für bestimmte Instanzen eine spezielle Implementation effizienter ist. Im Fall von Eq sind beide Funktionen durch die jeweils andere definiert, sodass es reicht, nur eine zu implementieren.
Um eine Instanz einer Typklasse zu definieren, schreibt man folgendes (Hier am Beispiel von Typ Bool):
instance Eq Bool where
True == True = True
False == False = True
_ == _ = False
Die Instanz überlädt nur die Funktion (==). Die Prüfung auf Ungleichheit ist, wie oben beschrieben, bereits automatisch als Negation der Gleichheit definiert. Mit Definition der Instanz kann die Prüfung auf Gleichheit nun auch für boolesche Werte verwendet werden.
Der Clou ist nun, dass man nicht zu wissen braucht, um welchen Datentypen es sich handelt, um eine Funktion einer Typklasse auf ihn anzuwenden. Es genügt, dass eine Instanz der Typklasse vorhanden ist. Diese Information kann in Haskell über eine Erweiterung des Typsystems hinzugefügt werden. Hier zum Beispiel die Funktion nub: Sie entfernt Duplikate aus einer Liste. Über die Elemente der Liste ist nur bekannt, dass sie Instanzen der Typklasse Eq sind. Dies wird über den Kontext Eq a vor der Typsignatur mitgeteilt:
nub :: Eq a => [a] -> [a]
nub [] = []
nub (x:xs) = x : nub (filter (/= x) xs)
Verwendungsbeispiele
Typklassen werden in der Sprache Haskell für viele Zwecke verwendet, z. B.:
Implementierung
Es gibt mehrere Wege, Typklassen zu implementieren. Der ursprüngliche und in den meisten Implementationen, einschließlich des Glasgow Haskell Compiler, verwendete Implementation von Typklassen wird im Folgenden erklärt.
Normalerweise implementiert man Typklassen, indem jede Typklasse durch einen Datentypen ersetzt wird. Er enthält als Felder die einzelnen Methoden der Typklasse. Wenn nun eine Funktion eine Instanz einer Typklasse für einen der Parameter benötigt, so wird ein Objekt des der gewünschten Typklasse zugehörigen Datentypes übergeben, welches die Instanz repräsentiert. Auf diese Weise wird für den endgültigen Code keine Erweiterung des bestehenden Typsystems benötigt. Man kann sich das am Beispiel der oben erwähnten Klasse Eq folgendermaßen vorstellen:
Die Typklasse Eq wird in einen Datentypen Eq übersetzt. (In einer echten Implementierung wird möglicherweise ein anderer Name benutzt) Dieser nimmt als Typparameter den zu instanziierenden Typen entgegen und hat die Felder der Typklassen als Methoden:
data Eq a = Eq (a -> a -> Bool) (a -> a -> Bool)
Für jede Instanz wird nun eine Variable vom Typ Eq erzeugt:
instanceEqBool :: Eq Bool
instanceEqBool = Eq eqBool (\a b -> not (eqBool a b)) where
eqBool True True = True
eqBool False False = True
eqBool _ _ = False
-- hier noch ein weiteres Beispiel: Der Einheitstyp ()
instanceEqUnit :: Eq ()
instanceEqUnit = Eq (\_ _ -> True) (\_ _ -> False)
Wenn jetzt eine Funktion den Kontext Eq a benötigt, so wird dies in einen zusätzlichen Parameter vom Typ Eq a übersetzt. Aus diesem Parameter werden anschließend die benötigten Methoden aufgerufen. Wenn eine aus dieser Funktion aufgerufene Funktion den Kontext ebenfalls benötigt, so wird er übergeben. Das Typsystem garantiert, dass die übergebenen Funktionen den richtigen Typ besitzen:
nub :: Eq a => [a] -> [a]
-- wird zu
nub :: Eq a -> [a] -> [a]
nub _ [] = []
nub (Eq _ (/=)) (x:xs) = x : nub (filter (/= x) xs)
Einzelnachweise
- Philip Wadler, Stephen Blott: How to make ad-hoc polymorphism less ad hoc. (Postscript) University of Glasgow, Oktober 1988, abgerufen am 19. Mai 2011 (englisch).