Implementing liftM2 in Haskell

Question

For an exercise, I've been trying to implement liftM2 using just the functions ap and liftM. The functions are defined as:

ap :: IO (a -> b) -> IO a -> IO b
liftM :: (a -> b) -> IO a -> IO b

liftM2 :: (a -> b -> c) -> IO a -> IO b -> IO c

I can easily do liftM2 using do notation but not sure how to do it using just ap and liftM. I was thinking of having the result be something that looks like this:

liftM2 f a b = liftM (_) (ap _ a)

I'm confused on how to mess with f, which is (a -> b -> c) such that I can just turn a to b and b to c. Thank you.

Where does that exercise come from? `liftM*` and `ap` are pretty much obsolete, the modern versions are `fmap`/`liftA*` and `<$>`. — leftaroundabout, Nov 07 '18 at 09:52

chi · Accepted Answer · 2018-11-04T22:27:43.113

The general pattern is transforming

liftMn f a1 ... an

into

f <$> a1 <*> ... <*> an
-- i.e., more precisely
(... ((f <$> a1) <*> a2) ... <*> an)

where <$> is liftM (AKA fmap) and <*> is ap.

Hence, for n=2 we get

(f `liftM` a1) `ap` a2
-- i.e.
ap (liftM f a1) a2

Checking the types:

f :: t1 -> t2 -> r
liftM f :: IO t1 -> IO (t2 -> r)
a1 :: IO t1
liftM f a1 :: IO (t2 -> r)
ap (liftM f a1) :: IO t2 -> IO r
a2 :: IO t2
ap (liftM f a1) a2 :: IO r

The key idea here is to read f :: t1 -> t2 -> r as f :: t1 -> (t2 -> r) so that liftM f :: IO t1 -> IO (t2 -> r) follows. Note the function type inside the IO. We can then "distribute" IO over -> using ap, so that we can apply a2 :: IO t2.

Thanks for explicitly noting the key idea. It is really insightful to consider $f$ working on just one argument as returning another function, which in turn expects a single argument. — The Coding Wombat, Apr 14 '21 at 09:28

score 0 · Answer 2 · answered Nov 06 '18 at 18:50

I think it's worth noting that your initial guess,

liftM2 f a b = liftM (_) (ap _ a)

isn't really that far off. But ap isn't quite the right place to start for that shape. Rather, consider

pairIO :: IO a -> IO b -> IO (a, b)
pairIO m n = do
  a <- m
  b <- n
  return (a, b)

Now, you can write

liftM2 :: (a -> b -> c) -> IO a -> IO b -> IO c
liftM2 f m n = liftM _ (pairIO m n)

GHC will tell you that it needs

_ :: (a, b) -> c

and you should be able to fill that very easily.

This actually reflects a common alternative formulation of the notion of an "applicative Functor":

class Functor f => Monoidal f where
  pur :: a -> f a
  pair :: f a -> f b -> f (a, b)

This class turns out to be equivalent in power to the standard Applicative class.

It turns out that you can actually combine actions in various ways, thanks to the Monoidal associative law. This looks like

xs `pair` (ys `pair` zs) = jigger <$> ((xs `pair` ys) `pair` z's)
   where
     jigger ((x, y), z) = (x, (y, z))

score 0 · Answer 3 · answered Nov 07 '18 at 09:44

With ap :: IO (a -> b) -> IO a -> IO b, we have both

  IO (a -> b)         {- and -}       IO (a -> b -> c)
  IO  a                               IO  a
  -----------                         ----------------
  IO       b                          IO      (b -> c)

thus we can combine two IO values with an IO binary function through

ap2 :: IO (a -> b -> c) -> IO a -> IO b -> IO c
ap2 mf mx my = ap mf mx `ap` my

             IO (a -> b -> c)
             IO  a
             ----------------
             IO      (b -> c)
             IO       b
             ----------------
             IO            c

or with a pure binary function,

liftM2 :: (a -> b -> c) -> IO a -> IO b -> IO c
liftM2 f mx my = ap2 (return f) mx my
               = ap (return f) mx `ap` my
               = (ap . return) f mx `ap` my

And what is the type of ap . return?

> :t ap . return
ap . return :: Monad m => (a -> b) -> m a -> m b

Why, it's the type of liftM! (here a more specific (a -> b -> c) -> IO a -> IO (b -> c))

              = liftM f mx `ap` my

Implementing liftM2 in Haskell

3 Answers3

Linked