Haskell：如果遍历参数，RWS 上的单子定点正在循环

Question

我正在编写一个涉及 RWS 的程序，用于跟踪可变状态并生成一些日志。我的目的是定义一个计算来评估某些操作，收集后续状态并根据它向 Writer 日志的 beginning 附加一些内容。最小示例：

type M = RWS () String [Int]

run a = evalRWS a () []

prepend s = tell (foldMap show s)

act = do
  tell "a"
  modify (1:)
  tell "b"

comp = mfix $ \s -> prepend s >> act >> get

在这里，我使用 MonadFix 通过在 act 发生之前写入日志来改变过去。它可以完美地返回 "1ab"。但是，如果我使用 M 遍历状态然后它挂起：

prepend s = forM_ s (tell . show)

这个行为对我来说很奇怪，我不明白为什么这个计算会发散。更难证明，因为第二个变体中的 prepend 不会在任何程度上改变状态。为什么这个程序不收敛？有什么办法可以修复 (inb4 "hehe fix") 它吗？

我知道我可以使用 RWS 的 State 部分来解决它，但出于某种原因我想避免它。

Answer 1

forM_ s u只有定义了s才会被定义，但是这里的s是mfix传递的一个占位符，整个计算过程中只会定义一次prepend s >> act >> get 终止。

您的第一个版本可以正常工作，因为它不需要检查状态即可将其配对。

mfix :: (a -> m a) -> m a 不接受严格函数 f :: a -> m a（即 f undefined = undefined）。

如果你有一个要 tell 的列表，那么一个更懒惰的方法是在告诉它们之前将它们连接起来：

prepend s = tell (concatMap show s)

Answer 2

发生这种情况是因为 forM_ 不是懒惰。 the mfix documentation 中明确指出了此要求：函数必须是惰性的，以便固定点收敛。但是 forM_ 确实需要解构它的参数以便迭代它。它仍然可以对列表的每个元素保持惰性，但不是列表本身。

当你运行你的这个递归式计算时，它需要三个步骤（即三个单子绑定）：prepend，然后 act，然后 get，结果你基本上得到一个看起来像这样的值：

[foldMap show s, "a", "b"]

foldMap show s 部分尚未计算 - 即它是一个指向 s 的 thunk，这是同一计算的最终状态。甚至可以在评估状态之前引用状态将其合并到 foldMap show s 表达式中，因为 Haskell 是惰性的。这是工作中的懒惰。

但是，如果将 prepend 替换为 foldM_，您的计算中将不再有三个步骤（三个一元绑定）。现在，您对结果状态列表的每个元素都有一个步骤。这意味着为了构建计算（即定义其步骤，也就是绑定），您需要检查其自身的结果状态。

Haskell：如果遍历参数，RWS 上的单子定点正在循环

Haskell: monadic fixpoint on RWS is looping if traversing on argument

monads

haskell

lazy-evaluation

monadfix

fixed-point-iteration