为什么州monad不可穿越？

Question

直觉上,在我看来,可以使用状态monad的遍历,例如:

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

但是状态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是a 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)

这个法律显然不成立,因为输出行动mappends而输入行动没有.好的,我们怎么样不这样做mappend:

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

这没有用,因为现在输出动作忽略了它的输入和替代,mempty而输入动作却没有.

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

如果我们能做到State (),为什么不State Bool呢？我们只需runState在原来的动作都 True和False,结果存储在一张地图,然后有结果状态行动在地图中进行查找.这适用于任何有限可枚举的状态域.有关详情,请参阅此答案.

Answer 2

被Traversable需要感Foldable; 但Statemonad不是 - 你不能foldMap,因为它的价值很简单,不在这里.

type State s = StateT s Indentity
newtype StateT s m a = State { runState :: s -> m (s, a) }

正如你所看到的,没有立即a折叠在这里,它是函数的唯一结果.