Are applicative functors composed with the applicative style really independent?

5
votes

I've come to understand functors, applicative functors, and monads as follows:

  • Functors: computations that can be mapped over.
  • Applicative functors: independent computations whose results can be combined together.
  • Monad: (possibly, but not necessarily) dependent computations that can be chained.

However, there is something about Applicative that conflicts with my understanding... Here is a Haskell example of a parser defined on the basis of more basic parsers using the applicative style:

(,) <$> parseName <*> parseEmail

The effects of the two parsers, parseName and parseEmail, are not independent, because they both consume tokens from the same input stream, e.g.

Jubobs [email protected]

parseEmail can only consume what hasn't been consumed by parseName. How, then, can the two computations be said to be independent?

1
haskellapplicative
Just because applicative functors expose an interface that can be used for independent computations doesn't mean that everything that satisfies this interface is parallelizable. Parsers are inherently sequential. – Alec
I guess your intuition about "independent" has to do with the fact that, unlike Monad, your parseName parser cannot make use of the parsed email "returned" by parseEmail. But of course what Applicative is is nothing more than the class and its associated laws. – jberryman

1 Answers

17
votes

The independence here is not saying that one computation cannot detect what other computations have been run - that is, it's not supposed to be the case that parseName has no effect on parseEmail. Rather, you cannot make use of the applicative value (the name parsed by parseName) to choose what applicative computation to run next: you can only ever parse a generic email, rather than, say, parsing an email address while checking that it does not contain the parsed name.

Another way of putting it is that if you use only applicative functions, the overall "shape" of your computation is predetermined ahead of time: you will always parse a name, followed by an email address. If you used monadic functions, you could make decisions about what to parse next based on the results of previous parses, letting you change the shape of your computation as it is running.