2009-12-24 45 views
16

我試圖把握Monad的狀態,爲此我想編寫一個monadic代碼,用一個線性同餘發生器產生一個隨機數序列(可能不是很好,但我的目的只是學習State Monad,而不是建立一個好的RNG庫)。State Monad,序列的隨機數和一元代碼

發電機就是這個(我想生成的Bool S表示簡單的順序):

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 

不要擔心的數字,這僅僅是(根據該種子的更新規則到數字食譜)應產生一個僞隨機序列Int s。現在,如果我想按順序產生隨機數我會怎麼做:

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

好了,我可以用一國單子避免這種情況的樣板:

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 

最後:

getNRandSt n = replicateM n nextVal 

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

好吧,這工作正常,並給我一個n僞隨機Bool s列表每個給定的種子。但...

我可以讀取我所做的(主要基於此示例:http://www.haskell.org/pipermail/beginners/2008-September/000275.html)並複製它以完成其他操作。但我不認爲我能理解符號和單子函數背後真正發生的事情(如replicateM)。

任何人都可以幫助我解決這些疑惑嗎?

1 - 我試圖解除nextVal函數來理解它的作用,但我不能。我猜可以提取當前狀態,更新它,然後將狀態傳遞給下一個計算,但這只是基於閱讀這個do-sugar,就好像它是英文一樣。

我該如何真正將這個函數解析爲原始的>> =並且一步一步地返回函數呢?

2 - 我無法掌握putget函數的功能。我可以猜測他們「打包」和「解壓縮」狀態。但do-sugar背後的機制仍然難以捉摸。

那麼,任何其他有關此代碼的一般評論是非常受歡迎的。我有時會跟Haskell一起合作,我可以創建一個可以工作的代碼,並且做我期望的代碼,但是我不能「跟隨評估」,因爲我習慣於使用命令式程序。

回答

30

國家monad起初看起來有些混亂,讓我們按諾曼拉姆齊的建議做,並從頭開始實施。警告,這很長!

首先,國家有兩個類型參數:包含狀態數據的類型和計算的最終結果的類型。這裏我們將分別使用stateDataresult作爲它們的類型變量。如果你仔細想想,這是有道理的。基於狀態的計算的定義特徵是它在產生輸出的同時修改狀態。

不太明顯的是該類型的構造需要功能從一個狀態到修改後的狀態和結果,就像這樣:

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

因此,儘管單子被稱爲「國家」,包的實際價值由monad得到的是的一個基於狀態的計算,而不是包含狀態的實際值。

記住這一點,我們不應該驚訝地發現用於在State monad中執行計算的函數runState實際上只不過是包裝函數本身的訪問器,並且可以像這樣定義:

runState (State f) = f 

那麼定義一個返回狀態值的函數是什麼意思?讓我們暫時忽略一個事實,即國家是一個單子,只看基本類型。首先,考慮此功能(這實際上不符合國家做任何事情):

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

如果你看一下國的定義中,我們可以看到,這裏的stateData類型是Int,而result類型Bool,因此由數據構造函數包裝的函數必須具有類型Int -> (Bool, Int)。現在,想象一下無國家版本的len2State--顯然,它會有String -> Bool。那麼如何將這樣一個函數轉換成一個返回適合於狀態包裝的值呢?

很明顯,轉換函數需要第二個參數,代表狀態值的Int。它還需要返回一個狀態值,另一個爲Int。由於我們在這個函數中並沒有對狀態做任何事情,所以讓我們做一些明顯的事情 - 把這個int傳遞給它。這裏是一個狀態函數,按照無狀態版本來定義:

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

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

但是這樣做很愚蠢和多餘。讓我們概括一下轉換,以便我們可以傳遞結果值,並將任何東西變成類似狀態的函數。

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) 

如果我們想要一個改變狀態的函數呢?顯然,我們不能用convert建立一個,因爲我們寫了這個來通過狀態。讓我們保持簡單,寫一個函數來用新值覆蓋狀態。它需要什麼類型的?它需要一個Int作爲新的狀態值,當然必須返回一個函數stateData -> (result, stateData),因爲這是我們的狀態包裝器所需要的。覆蓋狀態值在狀態計算之外並沒有真正的result值,所以我們的結果將只是(),這是在Haskell中表示「無值」的零元素元​​組。

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

很簡單!現在,我們實際上與該狀態數據做一些事情。讓我們從上面將len2State改寫成更明智的東西:我們將比較字符串長度和當前狀態值。

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

我們可以將它推廣到轉換器和無狀態函數嗎?就像我們之前做的那樣?不太容易。我們的len函數需要將狀態作爲參數,但我們不希望它「知道」狀態。的確很尷尬。但是,我們可以編寫一個快速幫助函數來處理我們所有的事情:我們將給它一個需要使用狀態值的函數,並且它將傳遞值並將所有內容打包回狀態函數離開len不明智。

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) 

現在,棘手的部分 - 如果我們想要將這些函數串在一起呢?比方說,我們希望對字符串使用lenState,如果結果爲false,則將狀態值加倍,然後再次檢查字符串,如果兩次檢查都返回true。我們擁有完成這項任務所需的所有部分,但全部寫出來將是一件痛苦的事情。我們可以創建一個函數來自動鏈接兩個函數,每個函數返回類似狀態的函數嗎?當然可以!我們只需要確定它有兩個參數:第一個函數返回的狀態函數和一個函數,該函數將前一個函數的result類型作爲參數。讓我們來看看它是如何變成了:

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

這一切正在做的是將第一狀態函數的一些狀態數據,然後將第二個函數的結果和修改後的狀態數據。很簡單,對吧?

現在,有趣的部分:在chainStatesconvert之間,我們幾乎應該能夠將無狀態函數的任意組合轉換爲啓用狀態的函數!我們現在唯一需要的是替換useState,它返回狀態數據作爲結果,以便chainStates可以將它傳遞給那些不知道我們正在使用的技巧的函數。另外,我們將使用lambdas接受前面函數的結果並給它們臨時名稱。好吧,讓我們做到這一點:

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) 

,並嘗試一下:

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

當然,我們不能忘記,國家實際上是包裝了類似於國家的職能,並保持我們的單子遠離他們,所以我們建造的漂亮功能都不會幫助我們實現真正的功能。或者他們會?在一個令人震驚的扭曲,事實證明,真正的國家單子都提供相同的功能,以不同的名字:

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) 

注意>> =幾乎是相同的chainStates,但有來定義它沒有什麼好辦法使用chainStates。因此,包裝的東西,我們可以使用真正國家重寫最後一個例子:

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) 

或者,所有蜜餞了相當於做記號:

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

很高興能讀到 – barkmadley 2009-12-24 09:10:40

+2

謝謝,儘管它可能已經在點上使用了更多的作品,但也很高興寫出來。我擔心人們可能會被推遲,但我想不是...... – 2009-12-25 01:00:16

7

首先,您的示例過於複雜,因爲它不需要將val存儲在狀態monad中;只有種子是持久狀態。其次,我認爲如果不是使用標準狀態monad,而是運用自己的類型重新實現所有狀態monad及其操作,那麼你將會有更好的運氣。我想你會以這種方式學習更多。這裏有一對夫婦的聲明,讓你開始:

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

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

然後,你可以寫你自己的連接詞:

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

最後

data Seed = Seed Int 
nextVal :: Mystate Seed Bool 

至於你的麻煩脫糖,您使用的do表示法非常複雜。 但是desugaring是一個一次性的機械程序。儘可能靠近我可以做出來,你的代碼應該desugar像這樣(要回你原來的類型和代碼,這點我不同意):

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

爲了使嵌套結構的更清楚一點,我已經對縮進採取了主要的自由。

4

你已經有了一個幾個很好的迴應。我在與國家monad合作時所做的工作是在我的腦海中用s -> (s,a)取代State s a(畢竟,這實際上就是這樣)。

然後你得到一個類型綁定,看起來像:

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

,你看到綁定僅僅是一種特殊的函數組合操作,如(.)

我就寫了一篇博客/教程州單元here。這可能不是特別好,但通過寫作讓我更好一些。