Ben wrote:
however, this does bring up a general question : why are applicative functors (often) faster than monads? malcolm wallace mentioned this is true for polyparse, and heinrich mentioned this is true more generally. is there a yoga by which one can write monadic functors which have a specialized, faster applicative implementation?
I'm not knowledgeable enough on the multicore stuff, but I can comment on the monad vs applicative issue. Applicative functors are not per se faster than monads, it's just that the former can encode static analysis while the latter can't. As you can see from the type of "bind" (>>=) :: m a -> (a -> m b) -> m b the structure of the computation in the second argument, i.e. its various side effects, can depend on a value of type a , which is only available at "run-time". In contrast, the type of "apply" (<*>) :: m (a -> b) -> m a -> m b makes it clear that the side effects are the same, no matter what the value of a will be at run-time. In other words, the structure of the computation is known statically. For parsers, interesting analyses are * Does a parser accept the empty set? * What are the first characters that a parser can accept? The answers can be obtained easily enough from an applicative functors, for instance acceptsEmpty (pure x) = True acceptsEmpty (f <*> g) = acceptsEmpty f && acceptsEmpty g But the corresponding analysis for monadic parsers is either harder or hopelessly inefficient because we don't know the structure of the parser until we run it on some input. See also this answer on StackOverflow: http://stackoverflow.com/a/7863380/403805 Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com