Wir denken deswegen Funktionen :: a -> b so erweitert, daß sie den Zählerstand (auf bestimmte Weise) benutzen und verändern dürfen. Sie bekommen jetzt den Typ :: a -> (Int -> (b, Int)). Den inneren Bestandteil (Int -> (b, Int)) nennen wir State Transformer (mit State Int und Resultat b).
Wir verstecken den Zähler dadurch, daß wir nur eine Operation gestatten: den Zählerstand ablesen und gleichzeitig erhöhen.
module State where data State a = State ( Int -> (a, Int) ) next :: State Int next = State ( \ s -> (s, s + 1) ) run :: State a -> a run (State f) = let (x, s) = f 1 in xDamit können wir das Inorder-Programm umschreiben:
module Monadic_Inorder where
import Prelude hiding (return)
import State
import Tree
import Anamorph
inorder :: Tree a -> Tree Int
inorder t = run ( transform t )
transform :: Tree a -> State (Tree Int)
transform Leaf = return Leaf
transform (Node { left = l, right = r }) =
bind ( transform l ) $ \ hl ->
bind ( next ) $ \ k ->
bind ( transform r ) $ \ hr ->
return ( Node { left = hl, key = k, right = hr } )
return :: a -> State a
return x = State ( \ s -> (x, s) )
bind :: State a -> (a -> State b) -> State b
bind (State f) g = State ( \ s0 ->
let (x, s1) = f s0
State h = g x
in h s1 )
Das sieht schon viel besser aus:
die Zugriffe auf den Zähler sind schön gekapselt.
Wir sehen wieder, wie "bind" Rechungen verbindet.
class Functor m => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
Das ist einer der wichtigsten Begriffe aus der Theorie und Praxis
der Funktionalen Programmierung der letzten zehn Jahre.
In der Kategorientheorie gibt es Monaden schon länger, und Eugenio Moggi schlug vor ca. 20 (?) Jahren vor, diese Konstruktion zur Beschreibung der Semantik von Programmen zu benutzen. Von Phil Wadler stammt der Gedanke, Monaden tatsächlich zu implementieren, und damit funktionale Programme zu strukturieren.
Nicht nur die Programme sehen besser aus, sondern Monaden sind ein Mittel, in einer rein funktionalen Sprache Rechnungen mit Nebenwirkungen zu bezeichnen. (Das Zähler-Erhöhen war eine "Nebenwirkung" des Markierens.) Das wird ganz kräftig benutzt bei der Gestaltung von Ein- und Ausgabe-Operationen in Haskell (die IO-Monade).