遍历单子谓词

Question

循环函数直到谓词成立

until :: (a -> Bool) -> (a -> a) -> a -> a

然而，一旦谓词具有以下形式，这就不够了

Monad m => (a -> m b)

我发现的唯一方法是通过显式递归，例如从句柄读取直到达到 EOF 时：

  (_, (Just stdout), _, _) <- createProcess (proc "task" (args fl)){ std_out = CreatePipe }
  let readH :: IO [Either String Task] -> IO [Either String Task]
      readH l = do eof <- hIsEOF stdout
                   if eof
                     then l
                     else do line <- hGetLine stdout
                             l' <- l
                             readH.return $ (eitherDecodeStrict' line) : l'
  out <- readH $ return []

有没有高阶函数可以简化这个？也许与 sequence 一起？

Answer 1

你可以自己定义一个"monadic until"函数，例如

untilM :: Monad m => (a -> m Bool) -> (a -> m a) -> a -> m a
untilM p f = go
  where
    go x = do r <- p x
              if r
                then return x
                else do a <- f x
                        go a

或者，如果您的谓词不需要参数，

untilM :: Monad m => m Bool -> (a -> m a) -> a -> m a
untilM p f = go
  where
    go x = do r <- p
              if r
                then return x
                else do a <- f x
                        go a

甚至，您根本不需要任何参数，

untilM :: Monad m => m Bool -> m a -> m ()
untilM p f = do r <- p
                if r
                  then return ()
                  else do f
                          untilM p f

Answer 2

让我们重构你的代码，直到我们得到这样一个组合器。

let readH :: IO [Either String Task] -> IO [Either String Task]
    readH l = do eof <- hIsEOF stdout
                 if eof
                   then l
                   else do line <- hGetLine stdout
                           l' <- l
                           readH.return $ (eitherDecodeStrict' line) : l'
out <- readH $ return []

首先我想指出多余的return。在此代码中，您永远不会调用 readH 而不附带 return。 readH 的参数实际上可以通过简单地删除不必要的 returns 来变得纯粹。请注意，我们必须在 then 分支上添加 return l，而不再需要在 else 分支上添加 "perform" l' <- l。

let readH :: [Either String Task] -> IO [Either String Task]
    readH l = do eof <- hIsEOF stdout
                 if eof
                   then return l
                   else do line <- hGetLine stdout
                           readH $ (eitherDecodeStrict' line) : l
out <- readH []

好的，为了清楚起见，现在我要重命名一些东西并稍微重新格式化。

let -- how to check the stop condition
    condition :: IO Bool
    condition = hIsEOF stdout
let -- what IO to do at each iteration
    takeOneStep :: IO ByteString
    takeOneStep = hGetLine stdout
let -- what pure work to do at each iteration
    pureTransform :: ByteString -> Either String Task
    pureTransform = eitherDecodeStrict'

let readH :: [Either String Task] -> IO [Either String Task]
    readH theRest = do
      isDone <- condition
      if isDone
        then return theRest
        else do
          raw <- takeOneStep
          readH (pureTransform raw : theRest)

out <- readH []

确保您了解此版本的代码与上一版本的代码有何相同之处；它只是有几个表达式被重命名和分解。

pureTransform 在这里有点转移注意力。我们可以将其与 takeOneStep 捆绑在一起。

let -- how to check the stop condition
    condition :: IO Bool
    condition = hIsEOF stdout
let -- what IO to do at each iteration
    takeOneStep :: IO (Eiter String Task)
    takeOneStep = do
      line <- hGetLine stdout
      return (eitherDecodeStrict' line)

let readH :: [Either String Task] -> IO [Either String Task]
    readH theRest = do
      isDone <- condition
      if isDone
        then return theRest
        else do
          thisStep <- takeOneStep
          readH (thisStep : theRest)

out <- readH []

此时重新阅读 readH 的正文。请注意，它的 none 不再特定于此特定任务。它现在描述了一种通用的循环 takeOneStep 直到 condition 成立。事实上，它一直都有那个通用结构！只是现在可以看到通用结构，因为我们已经重命名了特定于任务的位。通过制作函数的 takeOneStep 和 condition 参数，我们得到了所需的组合器。

untilIO :: IO Bool -> IO (Either String Task) -> [Either String Task] -> IO [Either String Task]
untilIO condition takeOneStep theRest = do
  isDone <- condition
  if isDone
    then return theRest
    else do
      thisStep <- takeOneStep
      untilIO (thisStep : theRest)

请注意，这个组合器在实现时不必限制为 Either String Task；它适用于任何类型 a 而不是 Either String Task.

untilIO :: IO Bool -> IO a -> [a] -> IO [a]

请注意，这个组合器在实现时甚至不必限制为 IO。它适用于任何 Monad m 而不是 IO.

untilM :: Monad m => m Bool -> m a -> [a] -> m [a]

这个故事的寓意是：通过为您的特定用例弄清楚如何通过显式递归编写 "looping over a monadic predicate"，您已经编写了通用组合器！它就在您的代码结构中，等待被发现。

有几种方法可以进一步清理，例如删除 [] 参数并按顺序构建列表（目前列表是颠倒的，您会注意到），但是那些超出了我现在要讲的重点，因此留作 reader 的练习。假设你已经完成了这两件事，你最终会得到

untilM :: m Bool -> m a -> m [a]

我会在你的例子中使用它：

(_, (Just stdout), _, _) <- createProcess (proc "task" (args fl)){ std_out = CreatePipe }
out <- untilM (hIsEof stdout) $ do
  line <- hGetLine stdout
  return (eitherDecodeStrict' line)

看起来很像命令式的 "until" 循环！

如果你交换参数顺序，那么你最终得到的结果几乎等同于 Control.Monad.Loops.untilM。请注意，与我们这里的解决方案不同，Control.Monad.Loops.untilM（令人讨厌！）总是在检查条件之前执行操作，因此如果您可能正在处理空文件，在这种情况下使用它不太安全。他们显然希望您使用 untilM 中缀，这使它看起来像 do-while，因此翻转了参数和 "body then condition" 废话。

(do ...
    ...
) `untilM` someCondition

遍历单子谓词

Looping over a monadic predicate

monads

haskell

predicate