How to make a IO (a->b) function from a -> IO b in Haskell

Question

I want to write a function that can list a directory recursively in breadth-first in Haskell. As you can see I need a function that can convert a (a -> IO b) to a IO (a->b). Simple as it seems, I can't make it. And I want to know how to do or whether it is possible.

dirElem :: FilePath -> IO [FilePath]
dirElem dirPath = do
  getDirectoryContents'' <- theConvert getDirectoryContents'
  return $ takeWhile (not.null) $ iterate (concatMap getDirectoryContents'') [dirPath] where
    getDirectoryContents' dirPath = do
      isDir <- do doesDirectoryExist dirPath
      if isDir then dirContent else return [] where
        dirContent = do
          contents <- getDirectoryContents dirPath
          return.(map (dirElem</>)).tail.tail contents
    theConvert :: (a -> IO b) -> IO (a -> b)
    theConvert = ??????????

Answer 1

This cannot be done. The reason is that the function can use its argument of type a to determine what IO action is executed. Consider

action :: Bool -> IO String
action True  = putStrLn "Enter something:" >> getLine
action False = exitFailure

Now if you'd convert it somehow to IO (Bool -> String) and evaluate this action, what should happen? There is no solution. We cannot decide if we should read a string or exit, because we don't know the Bool argument yet (and we may never know it, if the resulting function isn't called on an argument).

John's answer is a bad idea. It simply lets the IO action escape into pure computations, which will make your life miserable and you'll lose Haskell's referential transparency! For example running:

main = unsafe action >> return ()

will do nothing even though the IO action was called. Moreover, if we modify it a bit:

main = do
   f <- unsafe action
   putStrLn "The action has been called, calling its pure output function."
   putStrLn $ "The result is: " ++ f True

you'll see that the action that asks for an input is executed in a pure computation, inside calling f. You'll have no guarantee when (if at all) the action is executed!

Edit: As others pointed out, it isn't specific just to IO. For example, if the monad were Maybe, you couldn't implement (a -> Maybe b) -> Maybe (a -> b). Or for Either, you couldn't implement (a -> Either c b) -> Either c (a -> b). The key is always that for a -> m b we can choose different effects depending on a, while in m (a -> b) the effect must be fixed.

Answer 2

Petr Pudlák's answer is excellent, but I feel it can be generalized by abstracting away from IO, and looking at it from the point of view of the Applicative and Monad type classes.

Consider the types of the "combining" operations from Applicative and Monad:

(<*>) :: Applicative m => m (a -> b) -> m a -> m b
(>>=) :: Monad m => m a -> (a -> m b) -> m b

So you could say that your type a -> IO b is "monadic" while IO (a -> b) is "applicative"—meaning that you need monadic operations to compose types that look like a -> IO b, but only applicative operations for IO (a -> b)

There's a well-known intuitive statement of the "power" difference between Monad and Applicative:

• Applicative computations have a fixed static structure; what actions will be executed, what order they will be executed in, and the manner in which the results will be combined is known ahead of time.
• Monadic computations don't have such a fixed static structure; a monadic computation can examine the result value from one of its subactions and then choose between different structures at execution time.

Petr's answer is a concrete illustration of this point. I'll repeat his definition of action:

action :: Bool -> IO String
action True  = putStrLn "Enter something:" >> getLine
action False = exitFailure

Suppose we have foo :: IO Bool. Then when we write foo >>= action to bind action's parameter to foo's result, the resulting computation does nothing less than what my second bullet point describes; it examines the result of executing foo and chooses between alternative actions based on its value. This is precisely one of the things that Monad allows you to do that Applicative doesn't. You can't Petr's action into IO (Bool -> String) unless at the same time you predetermine which branch would be taken.

Similar remarks apply to augustss's response. By requiring that a list of values be specified ahead of time, what it's doing is making you choose which branches to take ahead of time, taking them all, and then allowing you to pick between their results.

Answer 3

You cannot create such function in a safe manner. Say we have f :: a -> IO b and g = theConvert f :: IO (a -> b). They are two very different functions f is an function that takes an argument of type a and returns an IO action with result b, where the io-action may depend on the argument given. g on the other hand is an IO action with as result a function a->b, the io-action cannot depend on any argument. Now to illustrate this problem lets lookat

theConvert putStr :: IO (String -> ())

Now what should it do when its run, it can certainly not print a given argument as it has no argument. Thus unlike putStr it can only do one action and then return some function of type String -> (), which has only one option const () (assuming no use of error or undefined).

---

Just as a side not, the other way around can be done, it adds the notion that the resulting action depends on the argument, while it actually does not. It can be written as

theOtherConvert :: IO (a -> b) -> (a -> IO b)
theOtherConvert m x = m >>= \f -> return $ f x

Though it works on any monad, or in applicative form theOtherConvert m x = m <*> pure x.

Answer 4

You cannot do it in a pure way in general, but if you can enumerate all the argument values you can perform all the IO upfront and return a pure function. Something like

cacheForArgs :: [a] -> (a -> IO b) -> IO (a -> b)
cacheForArgs as f = do
    bs <- mapM f as
    let abs = zip as bs
    return $ \ a -> fromMaybe (error "argument not cached") $ lookup a abs

cacheBounded :: (Enum a, Bounded a) => (a -> IO b) -> IO (a -> b)
cacheBounded = cacheForArgs [minBound .. maxBound]

But this function doesn't really help you much in your use case.