哈斯克尔.从纯代码到IO和返回

Question

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

我改变了问题.

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

关于使用IO:

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

据我所知,在算法中使用IO我们必须使用这样的函数:

obtainTree :: ByteString -> IO Tree

但我们可以避免吗？

Answer 1

当然你可以做到.您可以随时进行设置,以便将剩余的计算作为延续捕获,可以从外部恢复.

这是一种做这样的事情的方法:

-- 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

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