我应该使用什么递归方案来重复有效的操作，直到其结果与某个标准匹配?

Question

也就是说，我要问的是一个循环。

effectful :: Int -> IO Int
effectful n = do
putStrLn $ "Effect: " ++ show n
return n
condition = (== 3)
final :: Int -> IO ()
final n = putStrLn $ "Result: " ++ show n
loop = ?

它应该像这样工作：

λ loop [1..10]
Effect: 1
Effect: 2
Effect: 3
Result: 3

我可以提供一个递归定义：

loop (x: xs) = do
r <- effectful x
if condition r
then final r
else loop xs

但是，我很难用Functor、Monad、Foldable和Traversable方法，因为他们始终坚持评估所有行动， 而我需要的是停在列表中的某个点。

例如，使用unfoldrM(这是Data.List.unfoldr的有效版本，I 弥补了这个场合)我可以准确地执行我需要的动作，但我无法达到价值 最后一个操作，因为函数参数返回Nothing：

unfoldrM :: Monad m => (a -> MaybeT m (b, a)) -> a -> m [b]
unfoldrM f x = fmap reverse $ unfoldrM' f x (return [ ])
where
-- unfoldrM' :: (a -> MaybeT m (b, a)) -> a -> m [b] -> m [b]
unfoldrM' f x ys = runMaybeT (f x) >>= r -> case r of
Just (y, x') -> unfoldrM' f x' (fmap (y:) ys)
Nothing      -> ys
f :: [Int] -> MaybeT IO (Int, [Int])
f (x: xs) = (lift . effectful $ x) >>= y ->
if condition y
then MaybeT (return Nothing)
else lift . return $ (y, xs)

— 这让我想到："如果我改用Either，然后解开Left结果怎么办？这种考虑使我Control.Monad.Except，然后想到我应该将所需结果视为控制流中的异常。

exceptful :: Int -> ExceptT Int IO ()
exceptful n = do
r <- lift (effectful n)
if condition r
then throwError r
else return ()
loop' xs = fmap (fromRight ())
$ runExceptT (traverse_ exceptful xs `catchError` (lift . final))

 

λ loop' [1..10]
Effect: 1
Effect: 2
Effect: 3
Result: 3

我对这个解决方案的看法是它很糟糕。首先，使用 左侧作为实际的结果载体，其次，此代码比 我开始使用的递归loop。

能做什么？

Answer 1

我喜欢将这些类型的任务建模为涉及有效流的函数。流式处理包对此很有好处，因为它提供了一个与传统的纯列表非常相似的 API。(也就是说，Functor/Applicative/Monad实例有点不同：它们通过Stream"串联"来工作，而不是像在纯列表中那样探索所有组合。

例如：

import Streaming
import qualified Streaming.Prelude as S
loop :: Int -> (a -> Bool) -> IO a -> IO (Maybe a)
loop limit condition = S.head_ . S.filter condition . S.take limit . S.repeatM

使用repeatM、take、filter和head_"流"功能。

或者，如果我们有一个有效的函数和一个值列表：

loop :: (b -> Bool) -> (a -> IO b) -> [a] -> IO (Maybe b)
loop condition effectful = S.head_ . S.filter condition . S.mapM effectful . S.each

使用"流"中的each和mapM。

如果我们想执行最终的有效操作：

loop :: (b -> IO ()) -> (b -> Bool) -> (a -> IO b) -> [a] -> IO ()
loop final condition effectful = 
S.mapM_ final . S.take 1 . S.filter condition . S.mapM effectful . S.each 

使用"流"中的mapM_。

Answer 2

我的朋友，你忘记了一个base类，那就是Alternative。请考虑以下定义：

loop :: Alternative m => [m Int] -> m Int
loop = foldr (<|>) empty
effectful' :: Int -> IO Int
effectful' n = effectful n <* if condition n then return () else empty

现在你肯定可以看到它的去向：

λ loop (effectful' <$> [1..10]) >>= final
Effect: 1
Effect: 2
Effect: 3
Result: 3

你甚至可以在这里有一个无限的替代方案列表;如果保证最终其中一个不会被empty，整个循环是明确定义的。