CODEWITHSUNDEEP
haskellrecursionio
Leonid
Leonid

Reputation: 1157

Haskell. From pure code to IO and back

Are there a possibility to stop a recursive algorithm when it throws some exception provided by us, save it's state, ask user something and then continue the recursion from the saved place?

I changed the question.

I read a file system recursively and keep data in a tree. Suddenly I face with a hidden directory. Can I stop calculations and ask now user should I place information about the directory in my tree and then continue calculations?

About working with IO:

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

as I understand to work with IO inside the algorithm we have to use function like this:

obtainTree :: ByteString -> IO Tree

but can we avoid it?

Upvotes: 0

Views: 294

Answers (2)

Ankur
Ankur

Reputation: 33637

First thing first, a pure code cannot go to IO or we can say a pure function needs to become impure if it tries to use some impure function (i.e trying to use IO). In case you are wondering why this so, think about this: If the pure function ask the impure function about some data to complete its own processing then it looses "Referential transparency" because now the pure function can return different result for same input due to the involved impure (IO) call, hence it is no more pure.

Based on the above information, your solution will be as simple as making use of higher order function to ask the user about the information. Something like:

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

Here the (Directory -> IO Tree) is the function that will ask user about the required information and return a Tree data based on it.

Upvotes: 0

Carl
Carl

Reputation: 27003

Sure you can do it. You can always set things up so that you capture the remaining computation as a continuation, which can be resumed externally.

Here's one way to do something like this:

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

This lets you divide up your logic into an internal piece that runs inside Resumable and an external piece that handles the results of the internal part's prompting using whatever method it likes.

Here's a simple example of using this:

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

As a way of making this use case simpler, the module containing Resumable can be augmented to also export this function:

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

Which would allow rewriting main from that example as the somewhat simpler:

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

The one real issue with this approach is that every prompt must have the same type. Otherwise, it handles the problem nicely, using continuations to capture the rest of the computation implicitly when needed.

Upvotes: 6

Related Questions