How to define apply in terms of bind?

Question

In Haskell Applicatives are considered stronger than Functor that means we can define Functor using Applicative like

-- Functor
fmap :: (a -> b) -> f a -> f b
fmap f fa = pure f <*> fa

and Monads are considered stronger than Applicatives & Functors that means.

-- Functor
fmap :: (a -> b) -> f a -> f b
fmap f fa = fa >>= return . f

-- Applicative
pure :: a -> f a
pure = return

(<*>) :: f (a -> b) -> f a -> f b
(<*>) = ???  -- Can we define this in terms return & bind? without using "ap"

I have read that Monads are for sequencing actions. But I feel like the only thing a Monad can do is Join or Flatten and the rest of its capabilities comes from Applicatives.

join :: m (m a) -> m a
-- & where is the sequencing in this part? I don't get it.

If Monad is really for sequencing actions then How come we can define Applicatives (which are not considered to strictly operate in sequence, some kind of parallel computing)?

As monads are Monoids in the Category of endofunctors. There are Commutative monoids as well, which necessarily need not work in order. That means the Monad instances for Commutative Monoids also need an ordering?

Edit: I found an excellent page http://wiki.haskell.org/What_a_Monad_is_not

score 5 · Answer 1 · answered Nov 10 '19 at 13:18

5

We can copy the definition of ap and desugar it:

ap f a = do
   xf <- f
   xa <- a
   return (xf xa)

Hence,

f <*> a = f >>= (\xf -> a >>= (\xa -> return (xf xa)))

(A few redundant parentheses added for clarity.)

answered Nov 10 '19 at 13:18

chi

111,837
3
133
218

score 5 · Accepted Answer · edited Nov 10 '19 at 13:28

If Monad is really for sequencing actions then How come we can define Applicatives (which are not considered to strictly operate in sequence, some kind of parallel computing)?

Not quite. All monads are applicatives, but only some applicatives are monads. So given a monad you can always define an applicative instance in terms of bind and return, but if all you have is the applicative instance then you cannot define a monad without more information.

The applicative instance for a monad would look like this:

instance (Monad m) => Applicative m where
   pure = return
   f <*> v = do
      f' <- f
      v' <- v
      return $ f' v'

Of course this evaluates f and v in sequence, because its a monad and that is what monads do. If this applicative does not do things in a sequence then it isn't a monad.

Modern Haskell, of course, defines this the other way around: the Applicative typeclass is a subset of Functor so if you have a Functor and you can define (<*>) then you can create an Applicative instance. Monad is in turn defined as a subset of Applicative, so if you have an Applicative instance and you can define (>>=) then you can create a Monad instance. But you can't define (>>=) in terms of (<*>).

See the Typeclassopedia for more details.

As monads are Monoids in the Category of endofunctors. There are Commutative monoids as well, which necessarily need not work in order. By you definition of Monads as Sequencing Actions, that means the Monad instances for Commutative Monoids also need an ordering? — Pawan Kumar, Nov 10 '19 at 13:55
Sequencing is an *application* of monads, not a defining feature. Regular function composition also implements a type of sequencing: in `f (g x)`, you necessarily have to call `g` before `f`. — chepner, Nov 10 '19 at 14:20
Yes, its true that monads are not just about sequencing. I was skipping over that point as it isn't key to the question. — Paul Johnson, Nov 10 '19 at 15:20

score 2 · Answer 3 · edited Jul 15 '21 at 19:35

(<*>) :: f (a -> b) -> f a -> f b

(<*>) = ??? -- Can we define this in terms return & bind? without using "ap"

Recall that <*> has the type signature of f (a -> b) -> f a -> f b, and >>= has m a -> (a -> m b) -> m b. So how can we infer m (a -> b) -> m a -> m b from m a -> (a -> m b) -> m b?

To define f <*> x with >>=, the first parameter of >>= should be f obviously, so we can write the first transformation:

f <*> x = f >>= k      -- k to be defined

where the function k takes as a parameter a function with the type of a -> b, and returns a result of m b such that the whole definition aligns with the type signature of bind >>=. For k, we can write:

k :: (a -> b) -> m b
k = \xf -> h x

Note that the function h should use x from f <*> x since x is related to the result of m b in some way like the function xf of a -> b.

For h x, it's easy to get:

h :: m a -> m b
h x = x >>= return . xf

Put the above three definations together, and we get:

f <*> x = f >>= \xf -> x >>= return . xf

So even though you don't know the defination of ap, you can still get the final result as shown by @chi according to the type signature.

How to define apply in terms of bind?

3 Answers3

Linked