0

当递归算法抛出我们提供的一些异常时，是否有可能停止它，保存它的状态，询问用户一些东西，然后从保存的地方继续递归？

我改变了问题。

我递归地读取文件系统并将数据保存在树中。突然我面对一个隐藏的目录。我可以停止计算并现在询问用户我是否应该在树中放置有关目录的信息然后继续计算？

关于使用 IO：

obtainTree :: ByteString -> Tree
...
main = print $ obtainTree partition

据我了解，要在算法中使用 IO，我们必须使用如下函数：

obtainTree :: ByteString -> IO Tree

但我们能避免吗？

4

2 回答 2

6

当然你可以做到。您始终可以进行设置，以便将剩余的计算捕获为延续，可以在外部恢复。

这是执行此类操作的一种方法：

-- intended to be put in a module that only exports the following list:
-- (Resumable, Prompted, prompt, runResumable, extract, resume)
import Control.Applicative

newtype Resumable e r a = R { runResumable :: Either (Prompted e r a) a }

data Prompted e r a = P e (r -> Resumable e r a)

suspend :: e -> (r -> Resumable e r a) -> Resumable e r a
suspend e = R . Left . P e

instance Functor (Resumable e r) where
    fmap f (R (Right x)) = pure $ f x
    fmap f (R (Left (P e g))) = suspend e $ \x -> f <$> g x

instance Applicative (Resumable e r) where
    pure = R . Right
    (R (Right f)) <*> (R (Right x)) = pure $ f x
    (R (Left (P e f))) <*> x = suspend e $ \y -> f y <*> x
    f <*> (R (Left (P e g))) = suspend e $ \y -> f <*> g y

instance Monad (Resumable e r) where
    return = pure
    (R (Right x)) >>= f = f x
    (R (Left (P e f))) >>= g = suspend e $ \x -> f x >>= g


prompt :: e -> Resumable e r r
prompt e = suspend e pure

extract :: Prompted e r a -> e
extract (P e _) = e

resume :: Prompted e r a -> r -> Either (Prompted e r a) a
resume (P _ f) e = runResumable $ f e

这使您可以将逻辑划分为在内部运行Resumable的内部部分和使用它喜欢的任何方法处理内部部分提示结果的外部部分。

这是一个使用它的简单示例：

askAboutNegatives :: [Int] -> Resumable Int Bool [Int]
askAboutNegatives [] = return []
askAboutNegatives (x:xs) = do
    keep <- if x < 0 then prompt x else return True
    rest <- askAboutNegatives xs
    return $ if keep then x:rest else rest

main :: IO ()
main = do
    let ls = [1, -4, 2, -7, 3]
        loopIfNeeded (Right r) = return r
        loopIfNeeded (Left p) = do
            putStrLn $ "Would you like to keep " ++ show (extract p)
            i <- getLine
            loopIfNeeded $ resume p (i == "y")
    asked <- loopIfNeeded $ runResumable (askAboutNegatives ls)
    print asked

作为使这个用例更简单的一种方式，Resumable可以扩展包含的模块以导出这个函数：

runResumableWithM :: Monad m => (e -> m r) -> Resumable e r a -> m a
runResumableWithM f x = case runResumable x of
    Right y -> return y
    Left (P e g) -> do
        r <- f e
        runResumableWithM f $ g r

这将允许main从该示例重写为更简单：

main :: IO ()
main = do
    let ls = [1, -4, 2, -7, 3]
        ask x = do
            putStrLn $ "Would you like to keep " ++ show x
            i <- getLine
            return $ i == "y"
    asked <- runResumableWithM ask (askAboutNegatives ls)
    print asked

这种方法的一个真正问题是每个提示都必须具有相同的类型。否则，它会很好地处理问题，在需要时使用延续来隐式捕获其余的计算。

于 2013-10-22T19:26:51.963 回答
0

首先，纯代码不能进入 IO，或者我们可以说如果纯函数尝试使用某些不纯函数（即尝试使用 IO），则它需要变得不纯。如果您想知道为什么会这样，请考虑一下：如果纯函数向不纯函数询问某些数据以完成自己的处理，那么它就会失去“引用透明性”，因为现在纯函数可以为相同的输入返回不同的结果，因为所涉及的不纯（IO）调用，因此它不再是纯的。

基于以上信息，您的解决方案将像使用高阶函数向用户询问信息一样简单。就像是：

parseFileSystem :: FileSystem -> (Directory -> IO Tree) -> IO Tree

这(Directory -> IO Tree)是向用户询问所需信息并Tree基于它返回数据的函数。

于 2013-10-23T05:25:22.150 回答