Lift higher order function into monad

Question

Let's say I have a higher order function which performs some computation using values which it retrieves from it's functional parameter.

f :: a -> (b -> c) -> d

where a,b,c,d are some concrete types.

Then I have a function with this type

g :: b -> m c

where m is some monad.

Now is there a way to use g with f. That is turn f into a function which produces m d instead of d and can use g as it's second parameter?

A concrete example would be that m is the IO monad, f being a function computing sum of n numbers retrieved from its functional parameter and g reads a number from standard input.

f n g = sum $ map g (1..n)
g :: Int -> IO Int
g _ = readLn

I know there are functions for converting the standard input into a lazy list, which would solve this problem but my real situation is not that simple.

Suppose I have an algorithm for doing something on a graph. The algorithm uses a functional parameter to determine the neighbours of a node. This is so that I can have multiple implementations of the graph.

Now I want to use this algorithm with a non-deterministic graph (List monad) or a graph that is not fully known (Maybe monad). I know I could rewrite the algorithm to use monads and then use the identity monad for the basic case, but is this the only way? I think it would be easier to write the algorithm without monads.

Is this behaviour possible? I couldn't find a reason why it shouldn't be but I was not able to find a way how to do it.

Answer 1

So you want to e.g. derive mapM given map. That is you have a simple map:

map  :: (a -> b) -> [a] -> [b]

and you want to use it as a map on monadic structures

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

We can compute mapM from map by mapping the IO actions, then sequencing them, thus:

mapM f xs = sequence (map f xs)

And now we have the more general form, we can get back map by running mapM in the Identity monad. and then classic map is mapM in the identity monad.

> let g :: Int -> Identity Int
      g a = return (a^2)

where:

> runIdentity $ mapM g [1..10]
[1,4,9,16,25,36,49,64,81,100]

So yes, you need to generlize your higher order function to the right level -- be that monad, or functor, or applicative, then you are free to substitute in other notions of computation, including the identity.

You can mechanically rewrite any pure function to its monadic, by transformting the AST for the function:

• wrapping the result value in return
• identify newly-monadic subexpressions, and binding them.
• replacing variable binding with monadic bind; or, if it is applicative:
• replacing application with application in the monad (taking some care)

E.g.

map f []     = []
map f (x:xs) = f x : map f xs

To (applicative style)

mapM f []     = return []
mapM f (x:xs) = (:) <$> f x <*> mapM' f xs

or less clear, and fixing the evaluation order:

mapM f []     = return []
mapM f (x:xs) = do
    v  <- f x
    vs <- mapM f xs
    return (v:vs)

We can use applicatives for map, since there is no need for monadic bind to communicate results from one step to the next. Not so for foldl:

foldl        :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
     where
        lgo z []     =  z
        lgo z (x:xs) = lgo (f z x) xs

foldlM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
foldlM f z0 xs0 = lgo z0 xs0
     where
        lgo z []     = return z
        lgo z (x:xs) = do
            v <- f z x
            lgo v xs