Typeclassopedia
Funktoren, Monaden, Arrows: Typklassen für Typkonstruktoren

Vom Funktor zur Monade

Functor

Die Functor Typklasse ist eine der simpelsten Typklassen für Typkonstruktoren und dient als Basis für viele andere Typklassen. Sie hat nur eine Funktion:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

fmap

Die Funktion fmap hat zwei Parameter. Der zweite Parameter ist ein Wert der jeweiligen Instanz von Functor. Diese hat den Elementtyp a. Der erste Parameter ist eine Funktion, die einen Wert vom Typ a in einen Wert vom Typ b umwandelt, also in den Elementtypen des Rückgabewertes von fmap. Zur Veranschaulichung hier die Instanz von Functor für Listen und Maybe:

instance Functor [] where
  fmap g [] = []
  fmap g (x:xs) = (g x) : (fmap g xs)

instance Functor Maybe where
  fmap g Nothing = Nothing
  fmap g (Just x) = Just (g x)

Die Semantik von fmap lässt sich auf zwei Arten interpretieren:

• fmap wendet eine Funktion auf alle Elemente eines Containers an, ohne die Containerstruktur zu verändern.
• fmap wendet eine Funktion auf einen Wert an, ohne den Kontext des Wertes zu ändern.

• Bei der Liste handelt es sich um das Ergebnis einer nichtdeterministischen Berechnung.
• Der Wert vom Typ Maybe stellt eine Berechnung mit möglichem Fehlschlag dar. Ist der Wert Nothing steht für einen Fehler und eín Wert (Just x) für das erfolgreiches Berechnungsergebnis x.

class Functor f where
  fmap :: (a -> b) -> (f a -> f b)

Diese Signatur ist äquivalent zur ursprünglichen Signatur von fmap. Die Funktion fmap nimmt als Parameter ein Funktion a -> b und wandelt diese ein eine Funktion f a -> f b um. Die neue Funktion arbeitet im Kontext von des Funktors f. Dieser Vorgang wird häufig als liften von Funktionen bezeichnet.

Gesetze

Jede Instanz von Functor sollte die folgenden Gesetze erfüllen:

fmap id = id
fmap (g . h) = fmap g . fmap h

Diese beiden Gesetze stellen die strukturerhaltenden Eigenschaften, die schon in den beiden Semantiken von fmap angesprochen wurden, sicher, und bieten gleichzeitig einen Anstoß zur Optimierung. Wenn bei einer Datenstruktur das Traversieren mit fmap sehr aufwändig ist und der Aufwand des Anwendens der Funktion, die fmap übergeben wird, sehr gering, lassen sich zwei Aufrufe von fmap mit den Funktionen g und h zu einem Aufruf von fmap mit der Funktion (g . h) zusammenfassen.

Weitere Instanzen der Typklasse Functor

Der Typ ((,) e) entspricht einem Paar dessen erstes Element den Typ e hat. Dieser Wert vom Typ e stellt eine Anmerkung, oder möglicherweise eine Fehlermeldung zum Wert des zweiten Elementes dar. Dieser Typ lässt sich unter Zuhilfenahme einer weiteren Typklasse zur so genannten Writer Monade ausbauen.

instance Functor ((,) e) where -- entspricht sinngemäß "(e,)" ist aber leider syntaktisch nicht möglich
  fmap g (e,x) = (e,g x)

Der Wertebereich des Typkonstruktors ((->) r) umfasst alle einstelligen Funktionen die Werte vom Typ r akzeptieren und einen Wert eines beliebigen Typen zurückgeben. Ein konkreter Wert vom Typ (r -> a) kann als Menge von Werten vom Typ a angesehen werden, auf die durch Werte vom Typ r indiziert zugegriffen werden kann. ((->) r) wird auch als Reader Monade bezeichnet.

instance Functor ((->) r) where -- entspricht sinngemäß "(r ->)" ist aber leider syntaktisch nicht möglich
  fmap = (.)

Applicative

Die Typklasse Applicative erweitert die Typklasse Functor um zwei Funktionen:

class Functor f => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

Die erste Funktion pure nimmt einen Wert vom Typ a und setzt ihn in einen Kontext vom Typ f. Das ist meistens gleichbedeutend mit dem erzeugen eines Conatiners mit genau einem Element. Die zweite Funktion (<*>) ermöglicht es eine Funktion die in einem Kontext f steht auf einen, ebenfalls in einem Kontext stehenden, Wert a anzuwenden.

Neben den oben genannten Funktionen stellt die Typklasse Applicative die Funktion (<$>) bereit, welche die Infixvariante von fmap ist.

Für drei der bisher vorgestellten Instanzen von Functor lassen sich Instanzen von Applicative bilden:

Applicative Listen

instance Applicative [] where
  pure x = [x]
  gs <*> xs = [g x | g <- gs, x <- xs]

Die Implementierung von pure für Listen erzeugt lediglich eine einelementige Liste. (<*>) erwartet eine Liste von Funktionen vom Typ a -> b und eine Liste von Werten vom Typ a. Das ergebnis von (<*>) ist eine Liste aller Kombination von Funktionsanwendungen der ersten Liste auf die Elemente der zweiten Liste und demnach von Typ [b]. Dies ermöglicht eine nichtdeterministische Berechnung in eleganter Notation:

> (+) <$> [1,2,3] <*> [10,20,30]
[11,21,31,12,22,32,13,23,33]

• Zuerst wird durch <$> (entspricht fmap) die Liste [1,2,3] in eine Liste von Funktionen umgewandelt: [(1+),(2+),(3+)].
• Dann werden durch <*> Paare aus den Beiden Listen gebildet: [(1+)10,(1+)20,(1+)30,(2+)10,(2+)20,(2+)30,(3+)10,(3+)20,(3+)30]
• Die Auswertung ergibt: [11,21,31,12,22,32,13,23,33]

Applicative Maybe

instance Applicative Maybe where
  pure x = Just x
  _ <*> Nothing = Nothing
  Nothing <*> _ = Nothing
  (Just g) <*> (Just x) = Just $ g x

Für den Datentyp Maybe enthält die Implementierung von Applicative im wesentlichen nur drei Fälle für (<*>). Bei Abwesenheit (Nothing) der Funktion, oder des Wertes ist das Ergebnis von (<*>) auch Nothing. Die Implementierung von pure lässt nur diese eine Möglichkeit zu, was später noch durch die Gesetze der Typklasse Applicative verdeutlicht wird.

Applicative Reader Monade

instance Applicative ((->) r) where
  pure x = const x
  g <*> h = (\r -> g r $ h r)

pure wird durch eine einstellige Funktion implementiert, die unabhängig von der Eingabe immer den gleichen Wert x liefert. Durch die Implementierung von <*> werden zwei Reader Monaden zu einer verkettet.

Gesetze

bzw.

Das Liften einer Funktion g durch fmap und Anwenden auf einen kontextbehafteten Wert x ist identisch mit dem anwenden von <*> auf eine Funktion, die mit pure in einen Kontext gehoben wurde und einem kontextbehafteten Wert. So erklärt sich auch die Namensgebung der Funktion pure. Die Anwendung eines durch pure erzeugten Apllicative verändert den Kontext des zweiten Apllicative nicht.

Monad

Die Typklasse Monad sieht auf den ersten Blick wie der Beginn einer neuen Hierarchie von Typklassen aus:

class Monad m where
  return :: a -> m a
  (>>=)  :: m a -> (a -> m b) -> m b

Bei genauerer Betrachtung fällt jedoch schnell auf, dass die Signatur von return identisch mit Signatur der bereits vorgestellten Funktion pure aus der Applicative Typklasse ist. Die Funktion return hat die selbe Aufgabe wie pure und deshalb auch die selbe Implementierung.

Die Signatur der Funktion (>>=) (auch bind genannt) zeigt die eigentliche Neuerung gegenüber der Typklasse Applicative. Weiterhin wird ein kontextbefafteter Wert vom Typ m a in einer kontextbehafteten Wert vom Typ m b überführt. Diesmal jedoch wird der neue Kontext nicht nur durch die Implementierung der Typklasse, sondern auch noch durch die als zweiter Parameter übergebene Funktion vom Typ a -> m b, beeinflusst. Die Aufgabe der Funktion (>>=) ist es also, den Wert aus seinem Kontext zu lösen und mit Hilfe der übergebenen Funktion einen neuen Kontext sammt Wert zu erzeugen.

Für alle hier vorgestellten Instanzen von Applicative lassen sich Instanzen für Monad bilden:

Monad Listen

instance Monad [] where
  return = pure
  [] >>= _ = []
  (x:xs) >>= g = (g x) ++ (xs >>= g)
  -- Alternative mit fmap
  -- xs >>= g = concat $ fmap g xs

Die Implementierung von return ist identisch mit der von pure. Diese Implementierung kann bei allen Instanzen von Monad, die auch Applicativ implementieren, verwendet werden.

Die Funktion >>= erhält als ersten Parameter eine Liste mit Werten vom Typ a. Als zweiten Parameter eine Funktion g vom Typ a -> [b]. Die Funktion g wird elementweise auf die Liste angewendet und die so entstehenden Ergebnislisten konkateniert.

Monad Maybe

instance Monad Maybe where
  return = pure
  (Just x) >>= g = g x
  Nothing  >>= _ = Nothing

Für den Fall, dass der Wert Nothing ist gibt die Funktion >>= den Wert Nothing zurück, sonst das Funktionsergebnis von g x. So lassen sich jetzt Berechnungen mit Fehlern darstellen:

Just 3
>>= (\x -> Just (x + 1))
>>= (\y -> if odd y then Just y else Nothing)
>>= (\z -> Just (z - 1))

• 1. Zeile: Just 3 dient als Startwert der Berechnung.
• 2. Zeile: der bind-Operator bindet 3 an x. Die Funktion liefert das Ergebnis Just 4.
• 3. Zeile: der bind-Operator bindet 4 an y. Die Funktion liefert das Ergebnis Nothing.
• 4. Zeile: der bind-Operator liefert Nothing als Ergebnis der Berechnung.

Monad Monad Reader

instance Monad ((->) r) where
  return = pure
  g >>= h = (\r -> h (g r) r)

Der bind-Operator verkettet, ähnlich wie bei der Implementierung von Applicative mehrere Reader zu einem. Eine sehr einfacher Wert für einen Reader ist eine Funktion auf natürlichen Zahlen:

(*3)
>>= (\i -> if odd i then return i else return 0)
>>= (\i' -> return (i' `div` 3))
$ 3

• 1. Zeile: Die Berechnung startet mit der Reader-Funktion (*3), die alle Zahlen auf ihr Dreifaches abbildet.
• 2. Zeile: Die Funktion aus Zeile 1 wird komponiert mit einer weiteren Reader-Funktion. Dies geschieht abhängig vom Resultat der ersten Funktion. Ist das Resultat (das Dreifache der Eingabe der ersten Funktion) ungerade, wird mit einer konstanten Funktion komponiert, die eben diese Zahl Liefert. Anderenfalls wird mit einer Funktion komponiert, die alle Zahlen auf 0 abbildet.
• 3. Zeile: Die kombinierte Funktion aus Zeile 2 wird mit einer dritten Funktion komponiert, die das Ergebnis durch drei teilt.
• 4. Zeile: Die eigentliche Berechnung wird gestartet, indem die Funktion aus Zeile 1 bis 3 mit einem Wert (in diesem Fall 3) aufgerufen wird. Das Ergebnis der Berechnung ist 3.

Monad und Applicative

Wie anfangs angedeutet Besteht nur auf den ersten Blick kein Zusammenhang zwischen Monad und Applicative. Die fehlenden Hierarchie der Typklassen ist jedoch auf die Historie von Haskell zurückzuführen, da es Monad bereits vor Applicative gab.

Nützliche Hilfsfunktionen

Um die Hierarchie etwas deutlicher zu machen, hier ein paar Hilfsfunktionen:

liftM :: Monad m => (a -> b) -> m a -> m b
liftM g m = m >>= (\x -> return (g x))

Die Funktion liftM hebt eine Beliebige Funktion vom Typ a -> b in einen Monadischen Kontext. Dazu wird zuerst der Wert der sich in der Monade befindet mit Hilfe des bind-Operators geholt, dann die Funktion g darauf angewendet und schließlich das Ergebnis mittels return wieder in den monadischen Kontext gesetzt. Die Funktion liftM bietet somit die gleiche Funktionalität wie fmap aus der Typklasse Functor.

ap :: Monad m => m (a -> b) -> m a -> m b
ap mg m = mg >>= (\g -> m >>= (\x -> return (g x)))

Die Funktion ap ermöglicht es eine Funktion, die in einem monadischen Kontext steht auf einen monadischen Wert anzuwenden. Sie bildet das Pendant zur Funktion <*> aus der Typklasse Applicative.

Es lassen sich zu jeder Instanz von Monad Instazen von Functor und Applicative erzeugen, indem fmap als liftM, pure als return und <*> als ap definiert werden.

join :: Monad m => m (m a) -> m a
join mm = mm >>= id

Wenn der Inhalt einer Monade wieder eine Monade ist, kann es hilfreich sein diese Zusätzliche Schicht entfernen zu können. Die Funktion join übernimmt genau diese Aufgabe.

Unter Zuhilfenahme dieser drei Funktionen lässt sich nun eine alternative Definition der Typklasse Monad aufstellen:

class Applicative m => Monad' m where
  return :: a -> m a
  return = pure
  
  (>>=) :: m a -> (a -> m b) -> m b
  m >>= g = join $ fmap g m

  join :: m (m a) -> m a
  join mm = mm >>= id

Durch das Hinzufügen der Klassenhierarchie zu Apllicative ist es nun möglich return durch pure zu implementieren. Außerdem ist jetzt die Defition von >>= durch fmap und join möglich. Durch die zyklische Definition von >>= und join würde es ausreichen eine der beiden Funktionen zu implementieren um die volle Funktionalität von Monad zu erhalten. Dies ist besonders reizvoll, da die Definition von join meistens intuitiver und leichter verständlich ist:

instance Monad' Maybe where
  join Nothing = Nothing
  join (Just x) = x

instance Monad' [] where
  join = concat

instance Monad ((->) e) where
  join mm = \e -> mm e e