Monade di stato, sequenze di numeri casuali e codice monadico

Question

Sto cercando di cogliere la Monade di stato e con questo scopo volevo scrivere un codice monadico che generasse una sequenza di numeri casuali usando un generatore di congruenza lineare (probabilmente non buono , ma la mia intenzione è solo quella di imparare la Monade di Stato, non costruire una buona libreria RNG).

Il generatore è proprio questa (voglio generare una sequenza di Bool s 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 to Numerical Recipes) dovrebbe generare una sequenza pseudo-casuale di Int s. 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 dammi una lista di n pseudo-random Bool s per ogni seme dato. Ma ...

Posso leggere quello che ho fatto (principalmente basato su questo esempio: http://www.haskell.org/pipermail/beginners/2008-September/000275.html) e replicarlo per fare altre cose. Ma non credo di poter capire cosa sta realmente accadendo dietro le funzioni di notazione e monadici (come replicateM).

Qualcuno può aiutarmi con alcuni di questi dubbi?

1 - Ho provato a desugar la funzione nextVal per capire cosa fa, ma non ho potuto. Posso indovinare che estrae lo stato attuale, lo aggiorna e poi passa lo stato al calcolo successivo, ma questo si basa solo sulla lettura di questo do-sugar come se fosse inglese.

Come si desume veramente questa funzione per l'originale >> = e restituisce le funzioni passo-passo?

2 - Non riuscivo a capire cosa fanno esattamente le funzioni put e get. Posso immaginare che "impacchettano" e "scompattano" lo stato. Ma i meccanismi dietro il do-sugar sono ancora sfuggenti per me.

Bene, qualsiasi altra osservazione generale su questo codice è molto gradita. A volte cado con Haskell che posso creare un codice che funziona e fare ciò che mi aspetto che faccia, ma non posso "seguire la valutazione" come sono abituato a fare con programmi imperativi.

Answer 1

La monade di stato sembra un po 'confusa all'inizio; facciamo come suggerito da Norman Ramsey e spieghiamo come implementare da zero. Attenzione, questo è piuttosto lungo!

Primo, Stato ha due parametri di tipo: il tipo dei dati di stato contenuti e il tipo del risultato finale del calcolo. Useremo stateData e result rispettivamente come variabili di tipo per loro qui. Questo ha senso se ci pensi; la caratteristica che definisce un calcolo basato sullo stato è che modifica uno stato durante la produzione di un output.

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

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

Così mentre monade è chiamato "State", il valore effettivo avvolto dal monade è quello di un calcolo basato sullo 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 

Quindi cosa significa quando si definisce una funzione che restituisce un valore di stato? Ignoriamo per un momento il fatto che State è una monade, e guardiamo solo i tipi sottostanti. 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 racchiusa dal costruttore di dati deve avere il tipo Int -> (Bool, Int). Ora, immagina una versione senza stato di len2State - Ovviamente, sarebbe il tipo String -> Bool. Quindi, come procederesti a convertire una funzione del genere in una che restituisce un valore che si adatta a un wrapper State?

Bene, ovviamente, la funzione convertita dovrà prendere un secondo parametro, uno Int che rappresenta il valore dello stato. Deve anche restituire un valore di stato, un altro Int. Dal momento che non stiamo facendo nulla con lo stato in questa funzione, facciamo semplicemente la cosa ovvia - passiamo a quello di destra. 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 che specie di sciocco e ridondante. Generalizziamo la conversione in modo che possiamo passare il valore del risultato e trasformare qualsiasi cosa in una funzione di tipo statale.

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) 

Cosa fare se si desidera una funzione che modifichi lo stato? Ovviamente non possiamo costruirne uno con convert, dato che l'abbiamo scritto per passare lo stato. Rendiamolo semplice e scrivi una funzione per sovrascrivere lo stato con un nuovo valore. Che tipo di tipo avrebbe bisogno? Avrà bisogno di un Int per il nuovo valore di stato e, naturalmente, dovrà restituire una funzione stateData -> (result, stateData), perché è ciò di cui ha bisogno il nostro wrapper State. La sovrascrittura del valore di stato non ha un valore sensato di result al di fuori del calcolo dello stato, quindi il risultato qui sarà semplicemente (), la tupla a elementi zero che rappresenta "nessun valore" in Haskell.

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

È stato facile! Ora, facciamo in effetti fare qualcosa con i dati di stato. Riscriviamo len2State dall'alto in qualcosa di più sensato: confronteremo la lunghezza della stringa con il valore attuale dello stato.

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

Possiamo generalizzare questo in un convertitore e una funzione senza stato, come abbiamo fatto prima? Non abbastanza facilmente. La nostra funzione len dovrà prendere lo stato come argomento, ma non vogliamo che lo stato "sappia di". Imbarazzante, davvero Tuttavia, possiamo scrivere una funzione di aiuto veloce che gestisce tutto per noi: gli daremo una funzione che ha bisogno di usare il valore di stato, e passerà il valore in e quindi impacchetterà tutto in una funzione a forma di stato lasciando il len nessuno 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 mettere insieme queste funzioni? Diciamo che vogliamo usare lenState su una stringa, quindi raddoppiare il valore dello stato se il risultato è falso, quindi ricontrollare la stringa e infine restituire true se entrambi i controlli lo hanno fatto. Abbiamo tutte le parti di cui abbiamo bisogno per questo compito, ma scriverlo tutto sarebbe un problema. Possiamo creare una funzione che concatena automaticamente due funzioni che restituiscono ciascuna funzioni simili a quelle dello stato? Cosa certa! Dobbiamo solo accertarci di prendere come argomenti due cose: la funzione di stato restituita dalla prima funzione e una funzione che accetta il tipo result della funzione precedente 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, vero?

Ora, la parte interessante: tra chainStates e convert, dovremmo quasi essere in grado di trasformare qualsiasi combinazione di funzioni senza stato in una funzione abilitata dallo stato! L'unica cosa di cui abbiamo bisogno ora è la sostituzione di useState che restituisce i dati di stato come risultato, in modo che chainStates possa passarlo alle funzioni che non sanno nulla del trucco che stiamo sfruttando.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 provarlo:

> 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) 

Nota che >> = è quasi identica a chainStates, ma non c'era buon modo per definirla usando chainStates. Quindi, per avvolgere le cose, possiamo riscrivere l'esempio finale con lo Stato vera:

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) 

Oppure, 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, l'esempio è troppo complicato perché non è necessario memorizzare val nella monade di stato; solo il seme è lo stato persistente. Secondo, penso che avrai più fortuna se invece di usare la monade di stato standard, tu riattivi tutta la monade di stato e le sue operazioni tu stesso, con i loro tipi. Penso che imparerai 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 è piuttosto sofisticata. Ma il desugaring è una procedura meccanica line-at-a-time. 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' abbiamo preso maggiori libertà con la rientranza.

Answer 3

Hai una coppia 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 lo stato monad here. Probabilmente non è particolarmente buono, ma mi ha aiutato a migliorare le cose un po 'meglio scrivendolo.