Monadic sequence in terms of applicative functors

user_7825727 0
Viewed 119

Let's say we have a monadic sequence:

doSomething = do 
    a <- f 
    b <- g 
    c <- h 
    pure (a, b, c)

We can easily rewrite it using applicative functor:

doSomething2 = (,,) <$> f <*> g <*> h

But what if the monadic sequence looks like this:

doSomething' n = do 
    a <- f n 
    b <- g a 
    c <- h b 
    pure (a, b, c)

Is it still possible to use applicative there? If not, what is the hindrance? (Also it is written in a book that, despite this, we can use applicative and join together, but I don't see how to).

haskell
1 Answers

No, this is precisely the extra power that Monad brings compared to Applicative. A monadic, or applicative, value of type f a can be thought of as being two parts: the "effects" (stuff happening in the f data structure), and the "value" (stuff happening in the values of type a). With Applicative, it is impossible for the effects to depend on the value, because the functions in Applicative give you no way to weave a function's results (the value) back into the effect. The (>>=) function in Monad gives you this power; join is equivalently powerful.

The key is that the signature for (>>=) contains a function that looks like (a -> m b): you get to look at a pure value (a), and choose an effect (m b) based on that. Compare

(>>=) :: Monad m => (a -> m b) -> m a -> m b

to

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

The last two accept only functions that operate entirely in the value realm: (a -> b), and so cannot determine structure/effect based on values.

Of course you can still desugar this do notation, but you will have to use monadic operations in the result:

doSomething'' n =
  f n >>= (\a -> 
    g a >>= (\b -> 
      h b >>= (\c -> 
        pure (a, b, c))))
user_6254030
Related