monads - 状态单子(monad)如何工作？ (无代码说明)

Question

在过去的几个月里，我一直在花一些空闲时间来阅读有关 Monad 的文章。自从大学时代以来，我就没有使用过函数式语言。所以我不太记得 Haskell，当然也不知道 Scalaz。

学习洋葱、墨西哥卷饼和三明治，同时尝试将这些食物与大量 Haskell 代码关联起来，这是一段艰难的时光。幸运的是，我偶然发现了两篇关键的文章，这让我大吃一惊:图片中的单子(monad)，以及另一个来自命令式编码背景的人，他简单地写了以下内容:

a -> b becomes m[a] -> m[b] (functor)
a -> m[b] becomes m[a] -> m[b] (monad)
and applicative is just a "function with context"

连同描述bind目的的最简单的句子一起，许多类别的endofunctors爆炸并变得简单。

Identity、List、Maybe 等突然变得有意义了。在这些知识的插入下，我开始尝试使用单子(monad)类型在 C++ 中尝试一些 TMP，看看它会如何实现。

很快我就想传播状态。我想我现在读到的关于状态 monad 和 monad 转换器的文章比我一开始读的关于 monad 的文章还要多，但我一生都无法理解它们。我确信许多键盘已经磨损，因为这些主题上输入的所有单词都回答了像我这样的人。

但我请你再受苦一次。

a -> s -> (b, s)

函数接受一个值和某个状态，返回一个新值和(可能)修改后的状态。 Bind 显然需要将返回值和状态传播到下一个函数中。

我的问题是:monad 的工作是因为它们强加了一个结构。坚持结构并遵守法律会带来乐趣和彩虹。然而 a -> s -> (b, s) 看起来并不像一元 a -> m[b]。

即使应用了“a”，它仍然是 s -> (b, s)。区别在于后一个函数采用(单子(monad)？)STATE 并返回带有值的状态。而常规形式是:接受一个 VALUE 并返回一个 WRAPPED 值。

传入的参数以及返回类型的形式都会有所不同。然而许多文章都说这显然看起来像一个单子(monad)。对我来说肯定不是。

如果我要放松一下我被告知必须持有的观点:它不是将 m[a] 绑定(bind)到 a -> m[b]，而是采用对 monad 有意义的任何参数并将其应用于无论函数签名有意义...然后我就可以看到它的工作原理。

在这种情况下，我可以简单地说“哦，这个 monad 将 State[s] AND 'a' 绑定(bind)到像 a -> State[s] -> (State[s], b) 这样的函数”。然后它可以期望一个元组返回并将其解压到下一个函数的参数中。

但不知何故，我怀疑有一种方法可以使状态单子(monad)像所有其他单子(monad)一样工作 - 包括以某种方式期待 a -> m[b] 的形式(但它如何将状态贯穿其中？)。我怀疑这是可以做到的，因为我相信编写 Monad Transformers 将依赖于这些函数签名(形式？)的一致性。

即使您没有时间写出长篇大论的回复，从命令式程序员的角度来看一篇文章的链接也将是天赐之物。

(对任何错误使用术语表示歉意 - 我也在一路上学习这一点)

Answer 1

我认为正在讨论的 monad 实例确实保留了State结构，并且元组在不应该的情况下让你陷入了循环。

如果我们退后一步并询问 Bind 应该具有什么签名才能符合我们的 monad 期望，我们会得到:

(>>=) :: State s a -> (a -> State s b) -> State s b
someState >>= someFuncOfA = ...

我将在单子(monad)值构造函数周围放置额外的括号，记住它是 State 而不仅仅是 State 因为具体类型不能成为 Monad 的实例，只能是一个参数的类型构造函数:

(>>=) :: [State s] a -> (a -> [State s] b) -> [State s] b
someState >>= someFuncOfA = ...

其中 [State s] 将是所有 monad 中特殊的 m。

因为 State 的新类型是

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

我们知道，无论值构造一个 State 值意味着什么，该值采用的参数都是一个函数 s -> (a, s).

所以备份我们不完整的绑定(bind)定义:

(>>=) :: [State s] a -> (a -> [State s] b) -> [State s] b
someState >>= someFuncOfA = ...

我们知道 ... 必须是 State $ (someNewFunc) 因为这就是 State 获取值构造的方式。

第一个观察:元组与此没有太大关系。 函数 someNewFunc 只要它的类型与值构造 State 所需的类型相匹配，就可以维护我们想要的一元结构。事实上，该函数恰好需要类型s -> (a, s)，这几乎只是一种实现选择。签名可以是很多不同的东西，因为有 not really a difference between tuples and value constructors ，我确信您可以首先创建一个特殊的 data 类型，其值构造函数为此目的充当二元组，并使签名看起来人为地更好。

第二个观察结果:State 没有导出的 'State' 值构造函数，至少没有来自 Control.Monad.State，因此您使用辅助函数

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

它再次将函数作为其第一个参数，并在幕后进行值构造。

所以我们知道在绑定(bind)定义内部，我们将无法编写

someState >>= someFuncOfA = State $ (someFunc)

相反，它需要是

someState >>= someFuncOfA = state $ (someFunc)

和 state $ (someFunc) 计算时导致类型 State s a 因为 someFunc 被迫具有输入 (s -> (a,s)) 并且实际上会使用 runState 来完成此操作。

这可能不是一篇很好的文章。我尝试翻译 FP Complete State Monad tutorial 的相关部分。解决这个特定问题的东西。也许阅读会提供更好的描述。