Stato Monade, sequenze di numeri casuali e il codice monadica

Question

Sto cercando di cogliere lo Stato Monade e con questo scopo ho voluto scrivere un codice monadica che generare una sequenza di numeri casuali utilizzando un generatore congruenziale lineare (probabilmente non è buono, ma la mia intenzione è solo per imparare lo Stato monad, non costruire una buona biblioteca RNG).

Il generatore è proprio questa (voglio generare una sequenza di Bools per semplicità):

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 

Non preoccuparti per i numeri, questo è solo una regola di aggiornamento per il seme che (secondo Numerical Recipes) dovrebbe generare una sequenza pseudo-casuale di Ints. Ora, se voglio generare numeri casuali in sequenza farei:

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, così ho potuto evitare questo boilerplate utilizzando uno Stato Monade:

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

E infine:

getNRandSt n = replicateM n nextVal 

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

Ok, questo funziona bene e mi danno un elenco di n Bools pseudo-casuale per ogni data seme. Ma ...

posso leggere quello che ho fatto (soprattutto in base a questo esempio: http://www.haskell.org/pipermail/beginners/2008-September/000275.html ) e replicare per fare altre cose. Ma non credo di poter capire cosa sta realmente accadendo dietro le funzioni monadici (come replicateM) do-notazione e.

Qualcuno mi può aiutare con alcune di queste perplessità?

1 - Ho cercato di desugar la funzione nextval per capire ciò che fa, ma non ho potuto. Posso immaginare che estrae allo stato attuale, aggiorna e poi passare allo stato avanti per il prossimo calcolo, ma questo è solo sulla base di lettura di questo do-zucchero come se fosse inglese.

Come faccio davvero desugar questa funzione per l'originale >> = e restituire le funzioni passo-passo?

2 - Non riuscivo a capire quali funzioni esattamente la put e get fanno. Posso immaginare che essi "Pack" e "decomprimere" lo stato. Ma i meccanismi che stanno dietro il fai-da zucchero è ancora sfuggente per me.

Bene, tutti gli altri osservazioni di carattere generale su questo codice sono i benvenuti. A volte caduto con Haskell che posso creare un codice che funziona e fare quello che mi aspetto di fare, ma non posso "seguire la valutazione" come io sono abituato a fare con i programmi imperativi.

Answer 1

La monade Stato ha un aspetto tipo di confusione in un primo momento; facciamolo come suggerito Norman Ramsey, e camminare attraverso come implementare da zero. Attenzione, questo è abbastanza lunga!

Innanzitutto, Stato ha due parametri di tipo: il tipo di dati di stato di contenuti e il tipo di risultato finale del calcolo . Useremo stateData e result rispettivamente come variabili di tipo per loro qui. Questo ha senso se si pensa a questo proposito; la caratteristica che definisce un calcolo basato statale è che si modifica uno stato, producendo un'uscita.

Meno evidente è che il costruttore di tipo prende una funzione da uno stato ad uno stato modificato e di conseguenza, in questo modo:

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

Così, mentre la monade si chiama "Stato", il valore effettivo avvolto dalla monade è quello di un calcolo basato Stato-, non il valore effettivo dello stato contenuto.

Tenendo questo in mente, non dovremmo essere sorpresi di scoprire che la funzione runState utilizzata per eseguire un calcolo nella monade Stato è in realtà niente di più che una funzione di accesso per la funzione avvolto in sé, e potrebbe essere definita in questo modo:

runState (State f) = f

Che cosa significa quando si definisce una funzione che restituisce un valore di Stato? Ignoriamo per un momento il fatto che Stato è una monade, e basta guardare le tipologie di base. In primo luogo, prendere in considerazione questa funzione (che in realtà non fa nulla con lo Stato):

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

Se si guarda alla definizione di Stato, possiamo vedere che qui il tipo stateData è Int, e il tipo result è Bool, quindi la funzione avvolto dal costruttore dati deve avere il tipo Int -> (Bool, Int). Ora, immaginate una versione Stato-less di len2State - ovviamente, avrebbe tipo String -> Bool. Così come si va sulla conversione di una tale funzione in un unico restituendo un valore che si inserisce in un involucro Stato?

Beh, ovviamente, la funzione convertito avrà bisogno di prendere un secondo parametro, un Int che rappresenta il valore di stato. Inoltre deve restituire un valore di stato, un altro Int. Dal momento che non stiamo in realtà facendo nulla con lo Stato in questa funzione, facciamo solo fare la cosa più ovvia - pass che int destra attraverso. Ecco una funzione a forma di Stato, definito in termini di versione Stato-less:

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

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

Ma questo è il tipo di sciocco e ridondante. Cerchiamo di generalizzare la conversione in modo che possiamo passare al valore del risultato, e trasformare qualsiasi cosa in una funzione di stato simile.

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)

Che cosa succede se vogliamo una funzione che modifica lo stato? Ovviamente non possiamo costruire uno con convert, dal momento che abbiamo scritto che per passare lo Stato attraverso. Teniamolo semplice, e scrivere una funzione per sovrascrivere lo stato con un nuovo valore. Che tipo di tipo sarebbe bisogno? Sarà necessario un Int per il nuovo valore di stato, e, naturalmente, dovrà restituire una funzione di stateData -> (result, stateData), perché è quello che i nostri bisogni involucro di Stato. Sovrascrivendo il valore dello stato in realtà non hanno un valore result sensibile al di fuori del calcolo dello Stato, quindi il nostro risultato qui sarà solo (), lo zero-elemento tuple che rappresenta "nessun valore" in Haskell.

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

È stato facile! Ora, diamo davvero fare qualcosa con che i dati di stato. Riscriviamo len2State dall'alto in qualcosa di più sensato:. Confronteremo la lunghezza della stringa al valore attuale stato

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

Possiamo generalizzare questo in un convertitore e una funzione di stato-di meno, come abbiamo fatto prima? Non proprio la stessa facilità. La nostra funzione len dovrà prendere lo Stato come argomento, ma non vuole che "conoscere" lo stato. Awkward, anzi. Tuttavia, possiamo scrivere una funzione di supporto rapido che gestisce tutto per noi: abbiamo deciso di dargli una funzione che ha bisognoper utilizzare il valore di stato, e che passerà il valore e poi confezionare tutto il backup in una funzione a forma di Stato lasciando nessuno len il più saggio.

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)

Ora, la parte difficile - e se vogliamo stringa di queste funzioni insieme? Diciamo che vogliamo usare lenState su una corda, poi il doppio del valore di stato se il risultato è falso, quindi controllare la stringa di nuovo, e, infine, restituisce true se uno di controllo ha fatto. Abbiamo tutte le parti di cui abbiamo bisogno per questo compito, ma scrivere tutto fuori sarebbe un dolore. Possiamo fare una funzione che automaticamente catene insieme due funzioni che ogni ritorno funzioni di stato simile? Cosa certa! Abbiamo solo bisogno di assicurarsi che prende come argomenti due cose: la funzione di stato restituito dalla prima funzione, e una funzione che prende il tipo result della funzione preventiva come argomento. Vediamo come andrà a finire:

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

Tutto questo sta facendo sta applicando la prima funzione dello stato di alcuni dati di stato, quindi applicando la seconda funzione del risultato ei dati di stato modificato. Semplice, no?

Ora, la parte interessante: tra chainStates e convert, dovremmo quasi essere in grado di trasformare qualsiasi combinazione di funzioni dallo Stato meno in una funzione di Stato abilitato! L'unica cosa di cui abbiamo bisogno ora è un sostituto per useState che restituisce i dati di stato come il suo risultato, in modo che possano chainStates passarlo insieme alle funzioni che non sanno nulla circa il trucco stiamo tirando su di loro. Inoltre, useremo lambda ad accettare il risultato dalle funzioni precedenti e dare loro nomi temporanei. Va bene, facciamo questo accada:

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)

E provare:

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

Naturalmente, non possiamo dimenticare che Stato è in realtà una monade che avvolge le funzioni dello Stato-like e ci tiene lontano da loro, in modo da nessuna delle nostre funzioni nifty che abbiamo costruito ci aiuterà con la cosa reale. O lo faranno? In una torsione scioccante, si scopre che il vero Monade Stato fornisce tutte le stesse funzioni, con nomi diversi:

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)

Si noti che >> = è quasi identica a chainStates, ma non c'era buon modo per definirlo usando chainStates. Quindi, per avvolgere le cose, possiamo riscrivere l'ultimo esempio utilizzando il reale Stato:

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)

In alternativa, tutte candita con l'equivalente fare notazione:

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

Prima di tutto, il tuo esempio è troppo complicato, perché non ha bisogno di memorizzare il val nella monade Stato; solo il seme è stato persistente. In secondo luogo, credo che si avrà più fortuna se invece di utilizzare monade stato standard, si re-implementare tutti i Monade Stato e le sue operazioni da soli, con i loro tipi. Credo che si impara di più in questo modo. Qui ci sono un paio di dichiarazioni per iniziare:

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

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

Quindi è possibile scrivere i propri connettivi:

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

Infine

data Seed = Seed Int
nextVal :: Mystate Seed Bool

---

Per quanto riguarda il disturbo Dezuccheraggio, la notazione do che si sta utilizzando è abbastanza sofisticato. Ma Dezuccheraggio è una procedura meccanica line-at-a-tempo. Da quanto posso capire, il codice dovrebbe desugar come questo (che risale al i tipi di originali e di codice, che sono d'accordo con):

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

Al fine di rendere la struttura di nidificazione un po 'più chiaro, ho preso grandi libertà con l'indentazione.

Answer 3

Hai avuto un paio di grandi risposte. Quello che faccio quando si lavora con la monade Stato è nella mia mente sostituire State s a con s -> (s,a) (dopo tutto, questo è davvero quello che è).

Si raggiunge quindi un tipo di bind che assomiglia:

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

e si vede che si legano è solo una sorta specializzato di funzione di operatore di composizione, come (.)

Ho scritto un blog / tutorial su monade stato di qui . Probabilmente non è particolarmente buona, ma mi ha aiutato a Grok le cose un po 'meglio, scrivendo di esso.