Applicative Parser by Jim Duey.
In the next couple of posts, I’m going to show how to build a parser library based on the Free Applicative Functor and what you can do with it. To follow along, clone (or update) this repo. Then ‘lein repl’ and you should be able to copy the code to see what it does.
This post runs long (again). The code is really not that long and it’s mostly very small functions. But the amount of details hidden by the abstractions takes a lot of prose to explain. Which is actually one of the very real benefits of using these abstractions. They let you implement an enormous amount of functionality in very few lines of code with fewer bugs.
If you want to see what the point of all this prose is, skip to the “Other Interpretations” section at the bottom and then come back to see how it was done.
Warning: Heavy sledding!
You may want to start with: The basics of applicative functors, put to practical work [Haskell] by Bryan O’Sullivan, which parses “[an] application/x-www-form-urlencoded string.”
On the other hand, if you want the full explanation, consider Applicative Programming with Effects by Conor McBride and Ross Paterson. in Journal of Functional Programming 18:1 (2008), pages 1-13.
Abstract:
In this paper, we introduce Applicative functors–an abstract characterisation of an applicative style of effectful programming, weaker than Monads and hence more widespread. Indeed, it is the ubiquity of this programming pattern that drew us to the abstraction. We retrace our steps in this paper, introducing the applicative pattern by diverse examples, then abstracting it to define the Applicative type class and introducing a bracket notation which interprets the normal application syntax in the idiom of an Applicative functor. Further, we develop the properties of applicative functors and the generic operations they support. We close by identifying the categorical structure of applicative functors and examining their relationship both with Monads and with Arrows.
The page for McBride and Patterson’s paper points to later resources as well.
Enjoy!