Zustand Monad, Folgen von Zufallszahlen und monadischen Code

Question

Ich versuche, den Staat Monad und mit diesem Zweck zu begreifen Ich wollte einen monadischen Code schreiben, die eine Folge von Zufallszahlen unter Verwendung eines Kongruenzgenerator (wahrscheinlich nicht gut erzeugen würden, aber meine Absicht ist, nur den Staat zu lernen Monad, keine gute RNG-Bibliothek) bauen.

Der Generator ist gerade dieses (Ich möchte eine Folge von Bools der Einfachheit halber erzeugen):

type Seed = Int

random :: Seed -> (Bool, Seed)
random seed = let (a, c, m) = (1664525, 1013904223, 2^32)  -- some params for the LCG
                  seed' = (a*seed + c) `mod` m
              in  (even seed', seed')   -- return True/False if seed' is even/odd 

Mach dir keine Sorgen über die Zahlen, das ist nur eine Aktualisierungsregel für das Saatgut, dass (nach Numerical Recipes) sollte eine pseudo-zufällige Folge von Ints erzeugen. Nun, wenn ich der Reihe nach Zufallszahlen erzeugen möchte ich tun würde:

rand3Bools :: Seed -> ([Bool], Seed)
rand3Bools seed0  = let (b1, seed1) = random seed0
                        (b2, seed2) = random seed1
                        (b3, seed3) = random seed2
                    in  ([b1,b2,b3], seed3)

Ok, so kann ich diese vorformulierten vermeiden, indem Sie einen Staat Monad:

import Control.Monad.State

data Random {seed :: Seed, value :: Bool}

nextVal = do 
   Random seed val <- get 
   let seed' = updateSeed seed
       val'  = even seed'
   put (Random seed' val')
   return val'

updateSeed seed = let (a,b,m) = (1664525, 1013904223, 2^32) in (a*seed + c) `mod` m

Und schließlich:

getNRandSt n = replicateM n nextVal 

getNRand :: Int -> Seed -> [Bool]
getNRand   n seed = evalState (getNRandStates n) (Random seed True)

Ok, das funktioniert gut und geben Sie mir eine Liste von n pseudo-zufälligen Bools für jeden gegebenen Samen. Aber ...

kann ich lesen, was ich getan habe (vor allem auf der Grundlage dieses Beispiel: http://www.haskell.org/pipermail/beginners/2008-September/000275.html ) und replizieren es andere Dinge zu tun. Aber ich glaube nicht, kann ich verstehen, was wirklich passiert hinter der do-Notation und monadischen Funktionen (wie replicateM).

Kann mir jemand helfen mit einigen dieser Zweifel?

1 - Ich habe versucht, die NEXTVAL Funktion desugar zu verstehen, was es tut, aber ich konnte nicht. Ich kann mir denken, es den aktuellen Status extrahiert, aktualisiert sie und dann den Zustand voraus auf die nächste Berechnung passieren, aber das ist nur basierend auf der Lektüre dieser do-Zucker, als ob es Englisch war.

Wie kann ich wirklich desugar dieser Funktion der originalen >> = und Rückkehr Funktionen Schritt-für-Schritt?

2 - ich konnte nicht begreifen, was genau die put und get Funktionen tun. Ich kann mir denken, dass sie „packen“ und „auspacken“ der Staat. Aber die Mechanik hinter dem do-Zucker ist immer noch schwer für mich.

Nun, andere allgemeine Bemerkungen zu diesem Code sind sehr willkommen. Ich fiel manchmal mit Haskell, dass ich einen Code erstellen kann, das funktioniert und das tun, was ich erwarte, dass es zu tun, aber ich kann nicht „folgt der Auswertung“, wie ich bin mit zwingend notwendig, Programmen zu tun gewöhnt.

Answer 1

Der Staat Monade sieht Art zunächst zu verwechseln; wir tun, wie Norman Ramsey vorgeschlagen, und gehen Sie durch, wie von Grund auf neu zu implementieren. Achtung, das ist ziemlich lange!

Als erstes Bundesland hat zwei Typparameter: die Art der enthaltenen Zustandsdaten und der Typ des Endergebnis der Berechnung . Wir werden stateData und result verwenden jeweils als Typ Variablen für sie hier. Dies macht Sinn, wenn man darüber nachdenkt; das charakteristische Merkmal eines Staat basierte Berechnung ist, dass es einen Zustand ändert, während ein Ausgangssignal zu erzeugen.

Weniger offensichtlich ist, dass der Typ Konstruktor nimmt eine Funktion von einem Zustand in einen modifizierten Zustand und Ergebnis in etwa so:

newtype State stateData result = State (stateData -> (result, stateData))

Während also die Monade „State“ genannt wird, der tatsächliche Wert der Monade gewickelt ist, dass der ein Staat basierte Berechnung , nicht der tatsächliche Wert des enthaltenen Zustand.

Mit diesem Hintergedanken, sollten wir nicht finden überrascht sein, dass die Funktion runState verwendet, um eine Berechnung in dem Staat Monade auszuführen ist eigentlich nichts anderes als ein Accessor für die eingewickelt Funktion selbst und könnte wie folgt definiert werden:

runState (State f) = f

Also, was bedeutet es, wenn Sie eine Funktion, dass die Renditen ein Staat Wert definieren? Lassen Sie uns für einen Moment die Tatsache ignorieren, dass Staat eine Monade ist, und schauen Sie sich die zugrunde liegenden Typen. Zunächst betrachten diese Funktion (die eigentlich nicht mit dem Staat alles tun):

len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)

Wenn Sie bei der Definition des Staates betrachten, können wir sehen, dass hier der stateData Typ Int ist, und der result Typ ist Bool, so dass die Funktion durch die Daten Konstruktor gewickelt muss mit dem Typ Int -> (Bool, Int) hat. Nun stelle man einen Staat lose Version von len2State - offensichtlich wäre es Art String -> Bool haben. Wie würden Sie eine solche Funktion in einer gehen über das Konvertieren von einem Wert, der passt in einen Staat Wrapper Rückkehr?

Nun, natürlich, wird die umgewandelte Funktion benötigen einen zweiten Parameter zu nehmen, einen Int, die den Zustandswert. Es braucht auch einen Statuswert zurück, eine andere Int. Da wir nicht wirklich mit dem Staat in dieser Funktion etwas zu tun, lassen Sie sich nur die offensichtliche Sache tun - das int rechts weitergeben durch. Hier ist ein Staat förmige Funktion, definiert in Bezug auf die Staats weniger Version:

len2 :: String -> Bool
len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s i = (len2' s, i)

Aber das ist irgendwie albern und überflüssig. Lassen Sie uns verallgemeinern die Umwandlung, so dass wir in der Ergebniswert passieren kann, und schalten Sie alles in einem Staat ähnlichen Funktion.

convert :: Bool -> (Int -> (Bool, Int))
convert r d = (r, d)

len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s = convert (len2 s)

Was passiert, wenn wir eine Funktion wünschen, der den Zustand ändert? Natürlich können wir nicht eines mit convert bauen, da wir, dass schrieben über den Zustand zu übergeben. Lassen Sie uns halten Sie es einfach, und schreiben Sie eine Funktion, die den Zustand mit einem neuen Wert zu überschreiben. Welche Art von Typ würde es brauchen? Es wird eine Int für den neuen Zustandswert benötigen, und natürlich wird eine Funktion stateData -> (result, stateData) zurückzukehren, weil das, was unser Staat Wrapper Bedürfnisse. den Zustandswert zu überschreiben, dass es nicht einen vernünftigen result Wert außerhalb des Staates Berechnung hat, so dass unser Ergebnis hier wird nur () sein, der Null-Element Tupel, die „keinen Wert“ in Haskell darstellt.

overwriteState :: Int -> (Int -> ((), Int))
overwriteState newState _ = ((), newState)

Das war ganz einfach! Nun wollen wir eigentlich etwas tun mit, dass Zustandsdaten. Lassen Sie uns Rewrite len2State von oben in etwas mehr sinnvoll. Wir werden die String-Länge auf den aktuellen Zustandswert vergleichen

lenState :: String -> (Int -> (Bool, Int))
lenState s i = ((length s) == i, i)

Können wir das in einen Konverter verallgemeinern und einem Staat lose Funktion, wie wir zuvor? Nicht ganz so leicht. Unsere len Funktion muß den Staat als Argument nehmen, aber wir wollen es nicht Staat „wissen“. Peinlich, in der Tat. Jedoch können wir eine schnelle Hilfsfunktion dass Griffe alles für uns schreiben: wir werden es, dass der Bedarf eine Funktion gebenden Zustandswert zu verwenden, und es wird den Wert in und dann verpacken alles wieder nach oben in einen Staat förmigen Funktion verlassen len so klug wie zuvor.

übergeben

useState :: (Int -> Bool) -> Int -> (Bool, Int)
useState f d = (f d, d)

len :: String -> Int -> Bool
len s i = (length s) == i

lenState :: String -> (Int -> (Bool, Int))
lenState s = useState (len s)

Jetzt kommt der schwierige Teil - was passiert, wenn wir diese Funktionen zusammen zu bespannen wollen? Lassen Sie uns sagen, dass wir lenState auf einer Zeichenkette verwenden möchten, dann den Zustandswert verdoppeln, wenn das Ergebnis falsch ist, dann überprüfen Sie die Zeichenfolge wieder, und schließlich return true, wenn entweder Scheck tat. Wir haben alle Teile, die wir für diese Aufgabe brauchen, aber sie alle aus Schreiben ein Schmerz wäre. Können wir, dass jeder Rückkehr Staat ähnlichen Funktionen eine Funktion, die automatisch Ketten zusammen zwei Funktionen machen? Sichere Sache! Wir müssen nur sicherstellen, dass es als Argument zwei Dinge: die staatliche Funktion durch die erste Funktion zurückgegeben, und eine Funktion, die die vorherigen Funktion der result Typen als Argument. Mal sehen, wie es sich herausstellt:

chainStates :: (Int -> (result1, Int)) -> (result1 -> (Int -> (result2, Int))) -> (Int -> (result2, Int))
chainStates prev f d = let (r, d') = prev d
                       in f r d'

All dies tut, ist die erste Zustandsfunktion zu einigen Zustandsdaten anwenden, dann auf das Ergebnis die zweite Funktion der Anwendung und die modifizierten Zustandsdaten. Einfach, nicht wahr?

Nun, der interessante Teil: Zwischen chainStates und convert sollten wir fast in der Lage sein, jede Kombination von staatlich weniger Funktionen in einen Staat-fähige Funktion einzuschalten! Das einzige, was wir jetzt brauchen, ist ein Ersatz für useState dass kehrt die Zustandsdaten als Ergebnis, so dass chainStates es entlang zu den Funktionen passieren können, die nicht wissen nichts über den Trick, den wir auf sie sind zu ziehen. Außerdem werden wir lambdas verwenden Sie das Ergebnis aus den bisherigen Funktionen zu übernehmen und sie temporäre Namen. Okay, wir machen dies geschehen:

extractState :: Int -> (Int, Int)
extractState d = (d, d)

chained :: String -> (Int -> (Bool, Int))
chained str = chainStates  extractState         $ \state1 ->
              let check1 = (len str state1) in
              chainStates (overwriteState (
                  if check1 
                  then state1 
                  else state1 * 2))             $ \ _ ->
              chainStates  extractState         $ \state2 ->
              let check2 = (len str state2) in
              convert (check1 || check2)

Und probieren Sie es aus:

> chained "abcd" 2
(True, 4)
> chained "abcd" 3
(False, 6)
> chained "abcd" 4
(True, 4)
> chained "abcdef" 5
(False, 10)

Natürlich können wir nicht vergessen, dass Staat tatsächlich eine Monade ist, dass der Staat ähnlicher Funktionen wickelt und hält uns von ihnen weg, so dass keiner unserer netten Funktionen, die wir aufgebaut haben, wird uns die reale Sache helfen. Oder werden sie? In einer schockierenden Wendung, es stellt sich heraus, dass der wahre Staat Monade alle die gleichen Funktionen zur Verfügung stellt, unter verschiedenen Namen:

runState (State s) = s
return r = State (convert r)
(>>=) s f = State (\d -> let (r, d') = (runState s) d in
                         runState (f r) d')
get = State extractState
put d = State (overwriteState d)

Beachten Sie, dass >> = ist fast identisch mit chainStates, aber es gab keinen guten Weg, es zu definieren chainStates verwenden. Also, um die Dinge einpacken, können wir das letzte Beispiel mit dem neu zu schreiben real Status:

chained str = get                               >>= \state1 ->
              let check1 = (len str state1) in
              put (if check1 
                  then state1 else state1 * 2)  >>= \ _ ->
              get                               >>= \state2 ->
              let check2 = (len str state2) in
              return (check1 || check2)

Oder alle mit der äquivalenten do Notation kandierte up:

chained str = do
        state1 <- get
        let check1 = len str state1
        _ <- put (if check1 then state1 else state1 * 2)
        state2 <- get
        let check2 = (len str state2)
        return (check1 || check2)

Answer 2

Zunächst einmal ist Ihr Beispiel übermäßig kompliziert, weil es nicht die val im Zustand Monade zu speichern braucht; nur das Saatgut ist der persistente Zustand. Zweitens, ich glaube, du mehr Glück haben wird, wenn stattdessen die Standardzustand Monade verwenden, können Sie alle von der Monade Zustand neu implementieren und ihre Operationen selbst, mit ihren Typen. Ich glaube, Sie mehr auf diese Weise lernen. Hier sind ein paar Erklärungen für den Anfang:

data MyState s a = MyState (s -> (s, b))

get :: Mystate s s
put :: s -> Mystate s ()

Dann können Sie Ihre eigene Konnektive schreiben:

unit :: a -> Mystate s a
bind :: Mystate s a -> (a -> Mystate s b) -> Mystate s b

Schließlich

data Seed = Seed Int
nextVal :: Mystate Seed Bool

---

Wie für Ihre Mühe Entzuckern, die do Notation Sie verwenden, ist ziemlich anspruchsvoll. Aber Entzuckern ist eine Linie-at-a-time mechanisches Verfahren. So nahe, wie ich feststellen können, sollten Sie Ihren Code desugar wie diese (zurück zu Ihrem ursprünglichen Arten und Code, die ich nicht zustimmen):

 nextVal = get >>= \ Random seed val ->
                      let seed' = updateSeed seed
                          val'  = even seed'
                      in  put (Random seed' val') >>= \ _ -> return val'

Um die Verschachtelung etwas klarer zu machen, habe ich große Freiheiten mit dem Einzug genommen.

Answer 3

Sie haben ein paar große Antworten bekommen. Was ich tun, wenn mit dem Staat Monade ist in meinem Kopf ersetzen State s a mit s -> (s,a) (immerhin, das ist wirklich das, was es ist) zu arbeiten.

Sie dann einen Typen für bind erhalten, das aussieht wie:

(>>=) :: (s -> (s,a)) ->
         (a -> s -> (s,b)) ->
         (s -> (s,b))

und Sie sehen, dass bind ist nur eine Art von Funktion Zusammensetzung Operator spezialisiert, wie (.)

Ich schrieb einen Blog / Tutorial über den Zustand Monade hier . Es ist wahrscheinlich nicht besonders gut, aber hat mir geholfen, die Dinge ein wenig besser grok indem sie sie zu schreiben.