了解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。