http://www.paolocapriotti.com/assets/applicative.pdf
1.4 Example: applicative parsers The idea that monads are “too flexible” has also been explored, again in the context of parsing, by Swierstra and Duponcheel ([12]), who showed how to improve both performance and error-reporting capabilities of an embedded language for grammars by giving up some of the expressivity of monads. The basic principle is that, by weakening the monadic interface to that of an applicative functor (or, more precisely, an alternative functor), it becomes possible to perform enough static analysis to compute first sets for productions. The approach followed in [12] is ad-hoc: an applicative functor is defined, which keeps track of first sets, and whether a parser accepts the empty string. This is combined with a traditional monadic parser, regarded as an applicative functor, using a generalized semidirect product, as described in [10]. The question, then, is whether it is possible to express this construction in a general form, in such a way that, given a functor representing a notion of “parser” for an individual symbol in the input stream, applying the construction one would automatically get an Applicative functor, allowing such elementary parsers to be sequenced. Free applicative functors can be used to that end. We start with a functor f, such that f a describes an elementary parser for individual elements of the input, returning values of type a. FreeA f a is then a parser which can be used on the full input, and combines all the outputs of the individual parsers out of which it is built, yielding a result of type a.
Unfortunately, applying this technique directly results in a strictly less expressive solution. In fact, since FreeA f is the simplest applicative over f, it is necessarily just and applicative, i.e. it cannot also have an Alternative instance, which in this case is essential. We discuss the issue of Alternative in more detail in section 10.
Did Roma do what Capriotti thought is impossible? https://ro-che.info/articles/2013-03-31-flavours-of-free-applicative-functors https://ro-che.info/articles/2015-01-02-lexical-analysis
- Discussion and further work We have presented a practical definition of free applicative functor over any Haskell functor, proved its properties, and showed some of its applications. As the examples in this paper show, free applicative functors solve certain problems very effectively, but their applicability is somewhat limited. For example, applicative parsers usually need an Alternative instance as well, and the free applicative construction doesn’t provide that. One possible direction for future work is trying to address this issue by modifying the construction to yield a free Alternative functor, instead.
[10] R. Paterson. Constructing applicative functors. In MPC, pages 300– 323, 2012 [12] S. D. Swierstra and L. Duponcheel. Deterministic, error-correcting combinator parsers. In ADVANCED FUNCTIONAL PROGRAMMING, pages 184–207. Springer-Verlag, 1996.