Verständnis StateMonad

Question

Ich bin ein Haskell Anfänger und versuchen, diese Definition eines StateMonad zu verstehen, insbesondere die Bindeoperation. Es ist von Generalising Monads to Arrows Seite genommen 4.

instance Monad (StateMonad s) where 
    return a = SM (\s -> (a, s)) 
    x >>= f = SM (\s -> let 
          SM x' = x 
          (a, s') = x' s 
          SM f' = f a 
          (b, s'') = f' s' 
         in (b, s'')) 

Answer 1

Zuerst Sie die Art der >>= verstehen müssen; Ich gehe davon aus, dass du es tust, da es auf Seite 2 dieses Papiers steht und du hast es hinter dich gebracht.

Die Definition für Bind ist möglicherweise einfacher zu verstehen, wenn wir runState definieren.

newtype SM s a = SM (s -> (a, s)) 

runState :: SM a -> s -> (a, s) 
runState (SM f) s = f s 
-- this is equivalent to 
-- runState (SM f) = f 

runState läuft einen Zustand monadisch durch die Funktion, die das Extrahieren fs den Zustand und die Anwendung auf den Anfangszustand umwandelt. Die Funktion f gibt ein Tupel vom Typ (a, s) zurück. Das Tupel enthält den vom Zustand abhängigen Wert (vom Typ a) und einen neuen Zustand (vom Typ s). Im folgenden sind äquivalent

let (a, s') = runState x s 
in ... 

let SM x' = x 
    (a, s') = x' s 
in ... 

Beide extrahieren die Funktion x', wie der Zustand von x transformiert wird, dann gilt es auf einen Anfangszustand s. Das resultierende Tupel (a, s') enthält den zustandsabhängigen Wert a und den neuen Zustand s'.

Wir können die SM Mustererkennung in der Definition von >>= durch runState ersetzen.

x >>= f = SM (\s -> let 
         (a, s') = runState x  s 
         (b, s'') = runState (f a) s' 
        in (b, s'')) 

Jetzt werden wir Stück für Stück durchgehen.

Bind erstellt ein neues StateMonad mit einer Funktion, die von einem Anfangszustand s abhängt. Es gibt einen zustandsabhängigen Wert b und einen neuen Zustand s'':

x >>= f = SM (\s -> let 
         ... 
        in (b, s'')) 

Die zustandsabhängigen Wert a und ein neuer Zustand s' durch Ausführen des Zustandsmonadisch x mit dem Anfangszustand s berechnet werden:

     let 
         (a, s') = runState x  s 

Eine neue Zustandsmonade f a wird aus der vom Benutzer gelieferten Funktion f und dem zustandsabhängigen Wert a ermittelt. Diese zweite Zustands-Monade wird mit dem Zwischenzustand s' betrieben. Er berechnet einen anderen zustandsabhängigen Wert b und einen Endzustand s''.

      (b, s'') = runState (f a) s' 

Der zweite zustandsabhängigen Wert b und der Endzustand s'' sind, was durch die Funktion für den neuen StateMonad konstruiert zurückgegeben.

Answer 2

Eine etwas kürzere Antwort Cirdec ‚s ...

Erster zu ergänzen, daran erinnern, dass in x >>= f, x ist ein Zustand, Monade, f eine fn ist, die einen Zustand Monade zurückkehrt, und x >>= f ist auch ein Zustand Monade .

Die Grundidee ist wie folgt. Bei einem aktuellen Zustand s (der später geliefert wird, wenn wir die durch x >>= f dargestellte Statusmonade ausführen), möchten wir zuerst x mit s ausführen, was einen Wert a ergibt, zusammen mit einem neuen Zustand s'. Dann wollen wir f a ausführen, was uns eine weitere Zustands-Monade gibt. Wir wollen nicht nur diese resultierende Zustands-Monade f a mit irgendein Zustand obwohl laufen lassen; Stattdessen möchten wir es mit dem Zustand ausführen, der sich aus x ergibt, nämlich s', was uns einen neuen Wert b und einen neuen Status s'' gibt. x >>= f wird diese Berechnung von s -> (b, s'') darstellen.

Erinnern Sie sich: der ganze Punkt des Verwendens einer Zustandsmonade ist zu vermeiden, Staat ausdrücklich als ein anderer Parameter zu all unseren Funktionen weiterzugeben (das würde wirklich chaotisch, wirklich schnell werden). Die Idee hier ist also, den Zustand hinter den Kulissen richtig durchlaufen zu lassen, wenn wir Aktionen an eine Zustands-Monade binden.

Um dies zu tun, wir (1) Muster auf x Spiel die fn nach innen zu erhalten, dann (2) ausführen, um diese Funktion mit dem aktuellen Zustand ss' ein Ergebnis a und einigen neuen Zustand zu erhalten. Dann berechnen wir (3) f a, was eine Zustands-Monade zurückgibt, und ein Muster passt auf diese Monade, um das Fn nach innen zu bekommen; dann (4) führe das fn mit dem Zustand s' aus, um einen Wert b und einen Endzustand s'' zu erhalten. (1) bis (4) entsprechen den vier Zeilen, die unmittelbar auf let in Ihrem Code folgen. Was weißt du, wir haben gerade eine Fn von s bis (b, s'') definiert, die ordnungsgemäß im Hintergrund läuft. Jetzt wickeln wir das einfach in einen Konstruktor und wir sind fertig. x >>= f stellt jetzt eine Berechnung dar, die wir später ausführen können, indem wir einen Anfangszustand angeben.