在Haskell中使用状态（State）monad

Question

我一点一点地学习Haskell，并且正在努力理解State monad，试图编写一个函数，重复执行State计算，直到状态满足某个布尔测试，并将返回的值收集到列表中以获得总体结果。 最终我成功了：

collectUntil :: (s -> Bool) -> State s a -> State s [a]
collectUntil f s = do s0 <- get
                      let (a,s') = runState s s0
                      put s'
                      if (f s') then return [a] else liftM (a:) $ collectUntil f s

为了...

simpleState = state (\x -> (x,x+1))

*Main> evalState (collectUntil (>10) simpleState) 0
[0,1,2,3,4,5,6,7,8,9,10]

这个函数是否适合完成这个任务，或者有更符合习惯的方法?

- Dan T

---

惯用的方式很可能涉及到更多通用函数，例如 Monad m => m Bool -> m a -> m [a]。使用 monad-loops 中的 untilM，您可以得到：untilM simpleState (liftM (> 10) get)。 - Vitus

Answer 1

你正在犯我刚开始写单子代码时所犯的同样错误——让它过于复杂化，过度使用liftM并少用>>=（等同于少用<-符号）。

理想情况下，在状态单子中不必提及runState或evalState。你想要的功能如下：

- 读取当前状态 - 如果满足谓词f，则返回 - 否则，运行计算s并将其结果添加到输出中

你可以直接这样做：

collectUntil f comp = do
    s <- get                              -- Get the current state
    if f s then return []                 -- If it satisfies predicate, return
           else do                        -- Otherwise...
               x  <- comp                 -- Perform the computation s
               xs <- collectUntil f comp  -- Perform the rest of the computation
               return (x:xs)              -- Collect the results and return them

请注意，如果do语句属于同一个monad，您可以嵌套使用它们！这非常有用-它允许您在一个do块内分支，只要if语句的两个分支都导致相同monadic类型的内容。

该函数的推断类型为：

collectUntil :: MonadState t m => (t -> Bool) -> m a -> m [a]

如果您愿意，可以将其专门化为State s类型，但这并非必须：

collectUntil :: (s -> Bool) -> State s a -> State s [a]

如果您以后想使用不同的单子，甚至保留更通用的状态可能更好。

直觉是什么？

每当 s 是一个具有状态的计算并且您位于状态单子内部时，您可以执行以下操作：

x <- s

现在x将拥有计算结果（就像您调用了evalState并提供了初始状态一样）。如果您需要检查状态，可以执行以下操作：

s' <- get

并且s'将具有当前状态的值。

- Chris Taylor

---

谢谢，这非常有帮助。我认为我困惑的部分是将状态参数s视为完全独立的计算，我必须使用runState显式地评估它，并使用put将其结果状态注入到当前计算中。感谢@Heatsink提供的相同见解。 - Dan T

Answer 2

大多数单子都有一些基本的“运行”操作，比如runState、execState等。如果你经常在状态单子内部调用runState，那么就意味着你并没有真正使用单子提供的功能。你已经写出了

s0 <- get                    -- Read state
let (a,s') = runState s s0   -- Pass state to 's', get new state
put s'                       -- Save new state

您不必显式地传递状态。这就是状态单子的作用！您可以直接编写

a <- s

否则，该函数看起来是合理的。由于a在“if”语句的两个分支中都是结果的一部分，建议将其提取出来以增加清晰度。

collectUntil f s = step
  where
    step = do a <- s
              liftM (a:) continue
    continue = do s' <- get
                  if f s' then return [] else step

- Heatsink

Answer 3

对于这样的简单任务，我不会使用State单子。其他人已经澄清了如何编写单子版本，但是由于您要求以最惯用的方式编写单子，因此我想添加我的个人（更简单）解决方案。

collectWhile, collectUntil :: (a -> a) -> (a -> Bool) -> a -> [a]
collectWhile f cond z = takeWhile cond $ iterate f z
collectUntil f cond z = collectWhile f (not . cond) z

如果你只需要collectUntil，那么只需使用以下代码行：

collectUntil f cond z = takeWhile (not.cond) $ iterate f z

这里的takeWhile和iterate来自Prelude。为了完整起见，以下是（非常简单的）iterate代码，因为它是实现的核心：

iterate f x =  x : iterate f (f x)

警告：可能我的回答没有表达清楚，但是这个解决方案并不完全相同，因为我通过在State之外工作来融合状态和结果。当然，使用f :: (s, a) -> (s, a)，然后通过map fst或map snd进行投影，可以做出非常相似的事情，分别得到中间状态或结果列表。为了简化符号，在这一点上使用State的解决方案可能更简单。

- Riccardo T.

---

这并不是做同样的事情。它返回状态序列而不是结果序列。 - Chris Taylor

我知道，为了简单起见，我将State搁置不谈，将状态和结果融合在一起。很抱歉我的回答没有表达得够清楚。我的解决方案旨在处理像丹的示例中那样更简单的任务，其中状态和结果实际上是相同的（例如collectUntil (+1) (>10) 0 == [0,1,2,3,4,5,6,7,8,9,10]）。 - Riccardo T.