Estado de Mônada, sequências de números aleatórios e monádico código

Question

Eu estou tentando entender o Estado de Mônada e com este propósito que eu queria escrever um monádico código que poderia gerar uma sequência de números aleatórios, usando um Linear Congruential Generator (provavelmente não é bom, mas a minha intenção é apenas para saber o Estado de Mônada, que não construir uma boa RNG biblioteca).

O gerador é só isso (eu quero gerar uma seqüência de Bools por simplicidade):

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 

Não se preocupe com os números, esta é apenas uma regra de actualização para a semente que (de acordo com Numerical Recipes) deve gerar uma sequência pseudo-aleatória de Ints.Agora, se eu quiser gerar números aleatórios sequencialmente eu faria:

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, então eu poderia evitar esse clichê utilizando um Estado de Mônada:

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, finalmente:

getNRandSt n = replicateM n nextVal 

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

Ok, isso funciona bem e dá-me uma lista de n pseudo-aleatórios Bools para cada semente.Mas...

Eu posso ler o que eu fiz (principalmente com base neste exemplo: http://www.haskell.org/pipermail/beginners/2008-September/000275.html ) e replicá-lo para fazer outras coisas.Mas eu não acho que eu possa entender o que realmente está acontecendo por trás do fazer-notação e monádico funções (como replicateM).

Alguém pode me ajudar com algumas dessas dúvidas?

1 - eu tentei desugar a função nextVal para entender o que ele faz, mas eu não conseguia.Eu acho que ele extrai o estado atual, atualiza-lo e, em seguida, passar o estado de frente para a próxima computação, mas este é apenas baseado na leitura deste fazer-açúcar como se fosse inglês.

Como eu realmente desugar esta função original >>= e retorno de funções passo-a-passo?

2 - eu não conseguia entender o que exatamente a put e get funções.Eu acho que eles "pack" e "descompactar" o estado.Mas a mecânica por trás do fazer-de-açúcar ainda é indescritível para mim.

Assim, quaisquer outras observações gerais sobre este código são muito bem-vindos.Eu, às vezes, caiu com Haskell que eu posso criar um código que funciona e fazer o que eu espera, mas eu não posso "siga a avaliação" como eu estou acostumado a fazer com o imperativo programas.

Answer 1

O Estado de mônada faz parecer um pouco confuso à primeira;vamos fazer como Norman Ramsey sugeriu, e a pé, através de como implementar a partir do zero.Aviso, isso é muito demorada!

Primeiro, o Estado tem dois parâmetros do tipo:o tipo de continha dados do estado do e o tipo de resultado final da computação.Vamos usar stateData e result se, respectivamente, como as variáveis do tipo por aqui.Isso faz sentido se você pensar sobre isso;a característica definidora de um Estado-base de cálculo é que ele modifica um estado, ao mesmo tempo produzindo uma saída.

Menos óbvia é a de que o tipo de construtor tem um função a partir de um estado a para um estado modificado e o resultado, assim:

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

Assim, enquanto o monad é chamado de "Estado", o valor real envolvido pelo a mônada é a de um Estado-base de cálculo, não o valor real do contido estado.

Tendo isso em mente, não deveríamos ficar surpresos ao descobrir que a função runState utilizado para executar um cálculo no Estado mônada é, na verdade, nada mais do que um acessor para a função de quebra automática em si, e poderia ser definido assim:

runState (State f) = f

Então, o que significa quando você definir uma função que retorna um valor de Estado?Vamos ignorar por um momento o fato de que o Estado é uma mônada, e basta olhar para o subjacente tipos.Primeiro, considere essa função (que, na verdade, não fazer nada com o estado):

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

Se você olhar para a definição de Estado, podemos ver que aqui o stateData tipo é Int, e o result tipo é Bool, então, a função envolto pelos dados construtor deve ter o tipo de Int -> (Bool, Int).Agora, imagine um Estado-menos a versão de len2State- obviamente, ele teria tipo de String -> Bool.Então, como você ir sobre como converter uma função em uma que retorna um valor que se encaixa em um Estado de wrapper?

Bem, obviamente, o convertido função terá de ter um segundo parâmetro, um Int representa o valor de estado.Ele também precisa retornar um valor de estado, outro Int.Desde que nós não estamos realmente fazendo alguma coisa com o estado nesta função, vamos fazer a coisa mais óbvia--pass que int direito no meio.Aqui está um Estado em forma de função, definida em termos do Estado-menos de versão:

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

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

Mas que espécie de bobo e redundante.Vamos generalizar a conversão de modo que podemos passar o valor do resultado, e transformar qualquer coisa em um Estado como função.

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)

O que se queremos uma função que altera o estado?Obviamente, não podemos construir um com convert, desde que nos escreveu que, para passar do estado através de.Vamos mantê-lo simples e escrever uma função para substituir o estado, com um novo valor.Que tipo de tipo de precisaria?Ele vai precisar de um Int para o novo valor de estado e do curso de retorno de uma função stateData -> (result, stateData), porque isto é o que o nosso Estado wrapper necessidades.Substituindo o valor de estado não tem muito sensível result valor fora do Estado de cálculo, de modo que o nosso resultado aqui será apenas (), o zero-elemento da tupla que representa "sem valor", em Haskell.

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

Essa foi fácil!Agora, vamos, na verdade, fazer algo com que dados de estado.Vamos reescrever len2State de cima para algo mais sensato:vamos comparar o comprimento de seqüência de caracteres para o estado atual de valor.

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

Podemos generalizar esta em um conversor e um Estado menor função, como fizemos antes?Não tão facilmente.Nossa len função irá precisar de tomar o estado como um argumento, mas nós não queremos que ele "saber sobre" o estado.Estranho, de fato.No entanto, podemos escrever uma rápida função auxiliar que trata de tudo para nós:nós vamos dar uma função que precisa usar o valor de estado, e ele vai passar o valor e, em seguida, o pacote tudo de volta para um Estado em forma de função, deixando len nenhum o mais sábio.

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)

Agora, a parte difícil-o que se deseja cadeia estas funções juntos?Vamos dizer que nós queremos usar lenState em uma seqüência de caracteres, em seguida, duas vezes o valor de estado se o resultado for falso, em seguida, verifique a seqüência de caracteres de novo, e, finalmente, retorna true se verificar o fez.Temos todas as peças que precisa para esta tarefa, mas escrever tudo isso fora seria uma dor.Podemos fazer uma função que é automaticamente cadeias juntos duas funções que cada devolução, Estado-como funciona?Com certeza a coisa!Precisamos apenas certifique-se de que toma como argumentos duas coisas:a função do Estado devolvido pela primeira função, e uma função que leva a prévia da função result tipo como um argumento.Vamos ver como isso acontece:

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

Tudo isso está a fazer é aplicar a primeira função do estado para o estado de dados e, em seguida, aplicar a segunda função para o resultado e o estado modificado de dados.Simples, certo?

Agora, a parte interessante:Entre chainStates e convert, devemos ser capazes de transformar qualquer combinação de Estado-menos funções em um Estado habilitado para a função!A única coisa de que precisamos agora é uma substituição para o useState que retorna os dados do estado como seu resultado, de modo que chainStates pode passar para as funções que não sabe de nada sobre o truque estamos puxando-os.Além disso, nós vamos usar lambdas para aceitar o resultado das anteriores funções e dar-lhes nomes temporários.Ok, vamos fazer isso acontecer:

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 experimentá-lo:

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

Claro, não podemos esquecer que o Estado é, na verdade, uma mônada que envolve o Estado-como funções e nos mantém longe deles, para que nenhum dos nossos bacana funções que criamos vai nos ajudar com a coisa real.Ou será que eles vão?Em uma chocante reviravolta, verifica-se que o Estado real de mônada fornece todas as mesmas funções, sob diferentes nomes:

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)

Note que >>= é quase idêntico ao chainStates, mas não há uma boa maneira de defini-lo usando chainStates.Assim, para embrulhar as coisas, podemos reescrever o exemplo final, utilizando o real Estado:

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)

Ou, todos os cristalizadas com o equivalente a fazer a notação:

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

Primeiro de tudo, seu exemplo é excessivamente complicado porque não precisa armazenar o val na mônada do estado; Somente a semente é o estado persistente. Segundo, acho que você terá mais sorte se, em vez de usar a Mônada de Estado padrão, você implementa toda a Mônada do Estado e suas operações, com seus tipos. Eu acho que você aprenderá mais dessa maneira. Aqui estão algumas declarações para você começar:

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

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

Então você pode escrever seus próprios conectivos:

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

Finalmente

data Seed = Seed Int
nextVal :: Mystate Seed Bool

---

Quanto ao seu problema desusering, o do A notação que você está usando é bastante sofisticada. Mas o Desugaring é um procedimento mecânico de linha no tempo. O mais próximo possível, seu código deve desugar assim (voltando aos seus tipos e código originais, dos quais eu discordo):

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

Para tornar a estrutura de nidificação um pouco mais clara, tomei grandes liberdades com o recuo.

Answer 3

Você tem algumas ótimas respostas. O que faço ao trabalhar com a Mônada do Estado está em minha mente substituir State s a com s -> (s,a) (Afinal, é isso realmente o que é).

Você então recebe um tipo de ligação que se parece:

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

E você vê que o Bind é apenas um tipo de composição de função especializado, como (.)

Eu escrevi um blog/tutorial sobre a Mônada do Estado aqui. Provavelmente não é particularmente bom, mas me ajudou a fazer coisas um pouco melhor escrevendo -as.