Here's an interesting one: let's implement backtracking non-deterministic parsing as a Monad. If the code below is complex remember that it really is a near complete implementation of a backtracking non-deterministic parser from scratch using no libraries.
We'll do it first without any mention of the M-word. A parser is the kind of thing that consumes a string and returns a parsed value along with some "leftover" string data. For instance, a digit parser would look like (in Haskell types)
digitParse :: String -> (Int, String)
digitParse ('1' : leftover) = (1, leftover)
digitParse ('2' : leftover) = (2, leftover)
digitParse ('3' : leftover) = (3, leftover)
...
We can begin here and incrementally add more features. For instance, what happens when digitParse is applied to "foo". It ought to fail! To solve this, we'll introduce the Maybe (or Option) type
digitParse :: String -> Maybe (Int, String)
digitParse ('1' : leftover) = Just (1, leftover)
...
digitParse ('f' : leftover) = Nothing
...
Finally, if we have a parser which is sensitive to both apples and apricots then we might want to augment our return type with a notion of multiplicity of successes. We'll use a list for this and I want to note specially that we can now get rid of the notion of failure as represented by Maybe because we can use use the empty list ([]) to mean "parse failure".
All together we can call this type a Parser. A Parser which attempts to parse a polymorphic type can be considered as well, so we'll leave that as a type variable
newtype Parser a = Parser (String -> [(a, String)])
runParser :: Parser a -> String -> [(a, String)]
runParser (Parser f) = f
Now we can update the previous type `digitParse`
digitParse :: Parser Int
---
All by itself, Parsers aren't useful. We need to be able to combine them to make sense of a larger string. For instance, let's use the original notion of digitParser to build twoDigitParser
twoDigitParser :: String -> ((Int, Int), String)
twoDigitParser input = let (i1, leftover1) = digitParser input
(i2, leftover2) = digitParser leftover1
in ( (i1, i2), leftover2 )
Not too bad. We could even use recursion to parse a whole list of digits.
manyDigitParser :: String -> ([Int], String)
manyDigitParser input = let (i, leftover) = digitParser input
(is, leftover') = manyDigitParser leftover
in ( i : is, leftover' )
To make this truly work we'd want to layer in the notions of failure and non-determinism afforded by the Maybe type and the list type, but this simple example should suggest that writing all of this stuff out would be a LOT of boilerplate.
We'd like to build up to using monads to reduce all of that boilerplate. Ultimately we'll be able to define the fully non-deterministic `manyDigitParser` as
manyDigitParser :: Parser [Int]
manyDigitParser = do
i <- digitParser
is <- manyDigitParser
return (i : is)
Or even
manyDigitParser :: Parser [Int]
manyDigitParser = liftM2 (:) digitParser manyDigitParser
---
Monads depend on Functors, so we'll begin there. Functor just means that if we have a type Parser ty1 we can transform it into a type Parser ty2. For instance, let's say I have a function that converts lists of Int to a single Int by gluing digits together.
glueDigits :: [Int] -> Int
A Functor over Parser would let me turn manyDigitParser into integerParser
integerParser :: Parser Int
integerParser = fmap glueDigits manyDigitParser
To write it we need to define fmap polymorphically to just reach in modify the return type of our Parser. We'll destruct and reconstruct a Parser type to do this.
instance Functor Parser where
fmap modify (Parser parse) = Parser (\input ->
let results = parse f
in map (\(return, leftover) -> (modify return, leftover)) results
)
Now `integerParser` is perfectly valid code and Parser is an instance of Functor.
> :type fmap (+1) (undefined :: Parser Int)
fmap (+1) (undefined :: Parser Int) :: Parser Int
> :type fmap (\_ -> 3) (undefined :: Parser Char)
fmap (\_ -> 3) (undefined :: Parser Char) :: Parser Int
---
Now we get to the meat of things. We'll define a notion of Applicative, another superclass of Monad. Applicative just says two things--
1. We ought to be able to make a constant parser--one which always succeeds, always returns some constant value, and doesn't consume any input
constantParser :: a -> Parser a
constantParser a = Parser (\string -> [(a, String)])
2. We ought to be able to take a parser which returns a function and apply it to a parser which returns an input to that function as if they were regular values. We'll do so by running the function parser first and then the value parser and combining their results. In types that looks like
apParser :: Parser (a -> b) -> Parser a -> Parser b
apParser (Parser fparse) (Parser aparse) =
Parser (\input ->
[ (fun aval, aleftovers) | (aval, aleftovers) <- aparse fleftovers
, (fun, fleftovers) <- fparse input
]
)
The above syntax is just a list comprehension exactly like Python's. We use these two functions to form another typeclass instance for Applicative and reveal the generic names of constantParser and apParser
instance Applicative Parser where
pure = constantParser
(<*>) = apParser
---
Finally, we can move to the brunt of the problem: the Monad instance. Again, the entire goal here is just to abstract out the methods of sequencing parsers that we did manually at the very beginning. We'll do it first for the basic parser type.
newtype BasicParser a = BasicParser (String -> (a, String))
Monadic sequencing is a little strange to grasp at first. Like Applicative we need a way to inject constants into BasicParser.
instance Monad BasicParser where
return a = BasicParser (\input -> (a, input))
...
But we also need to somehow consolidate those
lets from above. To do this we'll write a function called bind (but written (>>=)) that has the type (BasicParser a -> (a -> BasicParser b) -> BasicParser b).
BasicParser parser >>= continuation =
BasicParser (\input -> let (a, leftovers1) = parser input
(b, leftovers2) = runParser (continuation a) leftovers1
in (b, leftovers2)
)
Notice how we had to use that exact same
let construct to define the parser? That's why it gets abstracted away.
We can do the same for the more general non-deterministic, failing parser
instance Monad Parser where
return = pure
Parser parser >>= continuation =
Parser (\input ->
[ (b, leftover2) , (b, leftover2) <- runParser (continuation a) leftover1
, (a, leftover1) <- parser input ]
)
---
So while that's a fairly large amount of abstract code, the end result is that we've embedded a fairly complex effect into our language—one that no reasonable language would have built in for you---non-determistic backtracking parsing. We can also centralize our optimizations of that parser into the monadic code and reap the benefits across the entire codebase.
Furthermore, most of what I wrote above, while abstract, requires almost no creativity as it just comes from recognizing that our Parser monad is a certain, standard combination of the State and List monads.