6

我一直在一点一点地学习一些 Haskell，并且正在（慢慢地）致力于理解 State monad，尝试编写一个重复状态计算的函数，直到状态满足一些布尔测试，并将返回的值收集到一个列表中以获得整体结果. 我终于成功了：

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]

这是该任务的合理功能，还是有更惯用的方法？

4

3 回答 3

10

您犯的错误与我第一次开始编写 monadic 代码时所犯的错误完全相同——使它变得过于复杂、过度使用liftM和未充分使用>>=（相当于，未充分使用<-符号）。

理想情况下，您根本不必提及runState或evalState在 state monad 中提及。您想要的功能如下：

  • 读取当前状态
  • 如果满足谓词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

请注意，如果它们是同一个 monad 的一部分，您可以嵌套 do 语句！这非常有用——它允许您在一个 do 块内进行分支，只要 if 语句的两个分支都指向相同的单子类型。

此函数的推断类型为：

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

如果您愿意，您可以将其专门用于该State s类型，尽管您不必：

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

甚至可能最好保留更一般的状态，以防您以后想使用不同的 monad。

直觉是什么？

每当s有状态计算并且您在状态单子中时，您都可以

x <- s

并且x现在将得到计算的结果（就像您evalState在初始状态下调用并输入一样）。如果你需要检查状态，你可以做

s' <- get

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

于 2012-06-28T19:01:34.040 回答
4

大多数 monad 都带有一些原始的“运行”操作，例如runState,execState等等。如果你经常在 state monadrunState 内部调用，这意味着你并没有真正使用 monad 提供的功能。你写

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
于 2012-06-28T18:41:37.607 回答
2

对于这样一个简单的任务，我不会使用Statemonad。其他人已经阐明了您实际上应该如何编写 monadic 版本，但我想添加我的个人（更简单）解决方案，因为您要求以最惯用的方式来编写它。

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 f x =  x : iterate f (f x)

警告：我的回答可能不够清楚，但这个解决方案并不完全相同，因为我通过在外面工作将状态和结果融合在一起State。当然，人们可以通过使用f :: (s, a) -> (s, a)然后投影map fst或map snd分别获得中间状态或结果列表来做非常相似的事情。不过，为了便于记号，将解决方案与 一起使用可能会更简单State。

于 2012-06-28T20:17:12.250 回答