haskell - 为什么状态单子(monad)不可遍历？

Question

直观地说，在我看来，可以将 traverse 与状态单子(monad)一起使用，例如:

traverse (\a -> [a, a+1]) (state (\s -> (1, s + 1))) 
  = [state (\s -> (1, s + 1), state (\s -> (2, s + 1)]

但是 state monad 没有实现 Traversable 类型类。这是为什么？我试图找出一种实现状态单子(monad)遍历的方法，似乎困难在于提取状态单子(monad)的结果，以便将其传递给作为遍历的第一个参数给出的函数。这是不可能的吗？

Answer 1

实现Traversable t ，你需要实现这个类型的函数:

sequenceA :: forall f a. Applicative f => t (f a) -> f (t a)

当 t是 State s ，这变成:

sequenceA :: forall f a. Applicative f => State s (f a) -> f (State s a)

显然我们不能为所有 s 编写一个实现。 ，因为我们必须知道如何创建 s或 f a无中生有才能继续。那将是一个矛盾。

但是可以编写一个满足 s 某些类的类型的实例。 .如果我们假设 s是 Monoid ，我们可以这样做:

instance (Monoid m) => Traversable (State m) where
  sequenceA (State run) = fmap (\a -> State (\s' -> (mappend s s', a)) fa 
    where (s, fa) = run mempty

但这不满足 Traversable法律。其中一项法律是:

traverse Identity = Identity

(回想一下 traverse f = sequence . fmap f )

这个定律显然不成立，因为输出 Action mappend s 而输入 Action 没有。好的，我们不要 mappend :

instance (Monoid m) => Traversable (State m) where
  sequenceA (State run) = fmap (\a -> State (\_ -> (s, a)) fa 
    where (s, fa) = run mempty

这无济于事，因为现在输出操作忽略其输入并替换为 mempty而输入 Action 没有。

这并不意味着没有类型 s我们无法为其构建合法的 Traverse (State s)实例。例如， State ()减少到 Identity ，这绝对是可遍历的。

如果我们能做到 State () , 为什么不 State Bool ?我们可以 runState两个 True 的原始操作和 False ，将结果存储在 map 中，然后让结果状态操作在该 map 中执行查找。这适用于任何有限可枚举的状态域。见 this answer详情。