CODEWITHSUNDEEP
haskellfunctional-programming
justan0therlurker
justan0therlurker

Reputation: 109

Implementing liftM2 in Haskell

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.

Upvotes: 4

Views: 547

Answers (3)

Will Ness
Will Ness

Reputation: 71065

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

Upvotes: 0

dfeuer
dfeuer

Reputation: 48591

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

Upvotes: 0

chi
chi

Reputation: 116139

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.

Upvotes: 7

Related Questions