在状态 monad 中使用 put with >>

Question

来自 Haskell 的功能思考（第 248 页）：

You can think of type State s a as being

type State s a = s -> (a,s)

...

put :: s -> State s ()
get :: State s s
state :: (s -> (a,s)) -> State s a

... state can be defined using put and get:

state f = do {s <- get; let (a,s') = f s;
              put s'; return a}

我认为可以这样重写：

get >>= \s ->
    let (a,s') = fs in
        put s' >> return a

那么 put s' 的目的是什么，如果 >> 丢弃了它的 return 价值？

Answer 1

>> 并没有丢弃第一个参数的所有内容。状态 monad 的定义（忽略 newtype）

a >> b = \s -> let (x, s') = a s in b s'

因此 >> 使用第一个参数的状态形式，但 'return value'（结果的 x 部分）被忽略。这就是状态 monad 的意义所在——跟踪状态的变化而程序员不必显式地考虑它们。

显然，OP 一直在阅读的内容并未正确解释这一点，因此您可以通过以下方式推导出上述定义。 >> 在所有 monad 中的定义是

a >> b = a >>= \ _ -> b

状态 monad（忽略 newtypes）的 >>= 的定义是

a >>= f = \ s -> let (x, s') = a s in f x s'

现在，将>>=的定义代入上面>>的定义并化简，我们得到：

a >> b = let f = \ _ -> b in \ s -> let (x, s') = a s in f x s'
    = \ s -> let (x, s') = a s in (\ _ -> b) x s'
    = \ s -> let (x, s') = a s in b s'

Answer 2

So what is the purpose of put s', if >> throws away its return value?

(>>) 确实丢弃了 return 值，但我们不使用 put 作为 return 值。 put 的类型是：

put :: s -> State s ()

return 的值是 put 的一个 ()，而 () 在大多数情况下只是一个无趣的占位符。 put 所做的有意义的部分——替换状态——没有反映在 return 值中。类似的情况是 putStrLn :: String -> IO ().

类型

Answer 3

State 是使用 monad 抽象来封装 effect 的示例。在这种情况下，具有操作效果很重要的操作是完全正常的，但它可能没有有意义的 return 值。

我会举例说明。考虑每个人最喜欢的递归算法，斐波那契数列：

fib :: Int -> Int
fib 1 = 0
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

我们都知道这是一种非常低效的计算这些数字的方法，但是如何低效呢？如果我们使用的是一种更小的语言，我们可能会试图破解一个可变变量并在每次调用 fib 时递增它。我们可以使用 State.

以纯函数的方式在 Haskell 中做类似的事情

让我们定义一个新版本的 fib:

fib' :: Int -> State Int Int
fib' 1 = modify (+1) >> return 0
fib' 2 = modify (+1) >> return 1
fib' n = modify (+1) >> (+) <$> fib' (n-1) <*> fib' (n-2)

现在我们可以同时计算第 n 个数字并计算调用了多少次：

> runState (fib' 7) 0
(8,25)
> runState (fib' 10) 0
(34,109)
> runState (fib' 30) 0  -- this takes about 5 seconds on my machine
(514229,1664079)

好的，这很好，但它如何回答问题？上面实现中需要注意的一点是modify (+1)。这具有将计数器加 1 的效果，但它本身没有任何有用的结果。我们使用 >> 将其与下一个操作排序，这确实有一个有用的结果，即计算。

在状态 monad 中使用 put with >>

Use of put with >> in the state monad

haskell

state-monad