Parsers in Scala built upon existing abstractions

After some initial struggles, the chapter Functional Parsers from the great book Programming in Haskell by Graham Hutton, where a basic parser library is built from scratch, significantly helped me to finally understand the core ideas of parser combinators and how to apply them to other programming languages other than Haskell as well.

While I recently revisited the material and started to port the examples to Scala I wasn't able to define a proper monad instance for the type Parser[A].

The type Parser[A] alias was defined like this:

type Parser[A] = String => Option[(A, String)]
// defined type alias Parser

To test the monad laws with discipline I had to provide an instance of Eq[Parser[A]]. Because Parser[A] is a function, equality could only be approximated by showing degrees of function equivalence, which is not a trivial task.

Also the implementation of tailRecM was challenging. (I couldn't figure it out.)

Using existing abstractions

Continue reading →