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] 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
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.)