瞭解Monadic斐波納契

Question

我正在學習haskell和學習單子。我看過和閱讀各種教程和編碼狀態單子一些簡單的例子，但我無法理解下面的一段代碼（從哈斯克爾維基取）：

import Control.Monad.State 
fib n = flip evalState (0,1) $ do 
    forM [0..(n-1)] $ \_ -> do 
    (a,b) <- get 
    put (b,a+b) 
    (a,b) <- get 
    return a 

我的問題歸結爲以下：

1. 什麼是在內部的第一條語句，即(a,b)<-get產生什麼結果。對於一些具體的例子，a和b的值如何。
2. 你爲什麼要在這裏使用狀態monad？

Answer 1

在此示例中，狀態是包含序列中生成的前兩個數字的對。這最初是(0, 1)提供給evalState。

類型的get是MonadState s m => m s這樣在內部do塊

(a, b) <- get 

取出的狀態對和分別結合a和b到所述第一和第二元件。狀態將在以下put中更新。

狀態將因此是：

(0, 1), (1, 1), (1, 2), (3, 2), (3, 5), ... 

外

(a, b) <- get 
return a 

解包的最終狀態值，並返回第一個元素。

Answer 2

首先讓我們明確正在使用的斐波那契算法。這個想法是從元組(0, 1)開始，然後找到下一個爲(1, 0 + 1)，下一個爲(1, 1 + 1)，(2, 2 + 1)，(3, 3 + 2)，依此類推。通常，步驟是\(a, b) -> (b, a + b)。你可以看到在這些元組中是斐波那契數。

什麼是內做的第一個語句，即沒有（A，B）< -get導致成什麼 裏面去？

Haskell沒有語句，只有表達式。

y <- x不是一個完整的表達式。它類似於x >>= \y ->。

y <- x 
m 

是一個完整的表達，相當於x >>= \y -> m。一行n非y <- n的形式相當於_ <- n（不包括let行，也許有些我忘了）。

使用這個我們可以desugar do-notation。

fib n = 
    flip evalState (0, 1) 
    (forM 
     [0..(n-1)] 
     (\_ -> get >>= (\(a, b) -> put (b, a + b))) 
    >>= (\_ -> get >>= (\(a, b) -> return a))) 
) 

現在它只是大概的瞭解>>=，return，get，put，等等。

狀態實際上只是s -> (s, a)類型的函數。他們採取初始狀態併產生下一個狀態加上一些其他值。

m >>= n又名「綁定」的類型爲Monad m => m a -> (a -> m b) -> m b。然後，如果我們的單子是State s，這是一樣的：

​​

的由m返回a將被傳遞到n。我們還能猜到什麼？我們預計國家也會傳遞，所以m返回的狀態也必須傳遞給n。函數m >>= n必須返回n返回的狀態和值。然後，我們知道如何實現綁定：

m >>= n = uncurry (flip n) . m 

return :: Monad m => a -> m a然後將其等同於return :: a -> s -> (s, a)：

return = flip (,) 

get :: State s s相當於get :: s -> (s, s)：

get = join (,) 

put :: s -> State s()或put :: s -> s -> (s,())：

put s _ = (s,()) 

evalState :: s -> State s a -> a或evalState :: s -> (s -> (s, a)) -> a：

evalState s f = snd (f s) 

可以展開的所有定義，看看究竟是什麼在發生的例子。儘管直覺應該就足夠了。

forM 
    [0..(n-1)] 
    (\_ -> get >>= (\(a, b) -> put (b, a + b))) 

我們不關心具有數字0到n - 1所以第一個參數被丟棄。 get檢索當前狀態，然後put寫入新狀態。我們這樣做n次。

>>= (\_ -> get >>= (\(a, b) -> return a))) 

我們不關心累計值（這是單位），所以第一個參數被丟棄。然後我們得到當前狀態並且只是項目的第一個元素。這是我們正在尋找的最終答案。

flip evalState (0, 1) … 

最後我們運行從初始狀態開始(0, 1)。

我們可以對此實現進行一些清理。首先，我們不關心範圍[0..(n-1)]，我們只關心重複動作n次。更直接的方式來做到這一點是：

replicateM n (get >>= \(a, b) -> put (b, a + b)) 

結果單元的列表，它是未使用的，所以更高效的版本是：

replicateM_ n (get >>= \(a, b) -> put (b, a + b)) 

已經存在的功能get後面跟put的共同格局，命名爲modify，定義爲\f -> get >>= put . f。因此：

replicateM_ n (modify (\(a, b) -> (b, a + b))) 

再有就是部分：

>>= (\_ -> get >>= (\(a, b) -> return a))) 

任何時候，我們不關心以前的結果，我們可以使用>>。

>> get >>= (\(a, b) -> return a)) 

這就是：

>> get >>= return . fst 

m >>= return . f簡化爲fmap f m：

>> fmap fst get 

現在我們有，總數：

fib n = 
    evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> fmap fst get 
) 
    (0, 1) 

我們也可以使用，比較：

fib n = 
    fst 
    (evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> get 
    ) 
    (0, 1) 
) 

然後因爲我傻了：

fib = 
    fst 
    . flip evalState (0, 1) 
    . (>> get) 
    . flip replicateM_ (modify (snd &&& uncurry (+))) 

你爲什麼要使用狀態單子在這裏？

你不會。這很清楚，因爲我們只使用狀態值;另一個值總是單位和丟棄。換句話說，我們只需要n（即找到哪個斐波納契數）在開始和之後我們只需要累加的元組。

有時您認爲有一串組合，如h . g . f，但您希望發送兩個參數而不是一個參數。那是State可能適用。

如果某些函數讀取並且某些函數寫入狀態（第二個參數），或者兩者都執行，那麼State就符合要求。如果只有讀者，則使用Reader，如果只有作者，則使用Writer。

我們可以改變這個例子來更好地使用State Monad。我會讓這個元組消失！

fib = 
    flip evalState 0 
    . foldr (=<<) (return 1) 
    . flip replicate (\x -> get >>= \y -> put x $> x + y) 

Answer 3

所以文檔狀態：get :: m s -- Return the state from the internals of the monad（見here）。

但我記得很清楚，當我試圖將我的頭包裹在State Monad上時，這並沒有多大幫助。

我只能推薦在ghci中使用:i和:t，並測試不同的子表達式。只是爲了感受它。像這樣的位：

import Control.Monad.State.Lazy 

runState (get) 0 
runState (get >>= \x -> put (x+1)) 0 
:t return 1 :: State Int Int 
runState (return 1) 0 
runState (return 1 >>= \x -> (get >>= \y -> return (x+y))) 0 

-- Keeping a pair of (predecessor/current) in the state: 
let f = (get >>= (\(a,b) -> put (b,a+b))) :: State (Int, Int)() 
runState (f >> f >> f >> f >> f >> f) (0,1) 

-- only keeping the predecessor in the state: 
let f x = (get >>= (\y -> put x >> return (x+y))) :: State Int Int 
runState (return 1 >>= f >>= f >>= f >>= f >>= f >>= f) 0 

而且玩弄modify，runState，evalState，execState。