"Monadic Parsing in Haskell" is an excellent tutorial by Erik Meijer and Graham Hutton on defining recursive descent parsers in Haskell.
Something I found interesting about the paper was the choice to
represent the success of a parser as a single-element list of results,
and the failure of a parser as an empty list of results. I like to use
optional types (e.g. Haskell's Maybe
or Scala's
Option
) to represent these all-or-nothing cases, and in
this post I explore the switch to such pattern.
From the paper, we get a defined parser type and a single-character consuming parser:
newtype Parser a = Parser (String -> [(a,String)])
item :: Parser Char
= Parser (\cs -> case cs of
item "" -> []
:cs) -> [(c,cs)]) (c
Replacing the result list with a Maybe
is
straightforward:
newtype Parser a = Parser (String -> Maybe (a,String))
item :: Parser Char
= Parser (\cs -> case cs of
item "" -> Nothing
:cs) -> Just (c,cs)) (c
Next, the Parser
is made into a Monad
, and
things start to get tricky:
instance Monad Parser where
return a = Parser (\cs -> [(a,cs)])
>>= f = Parser (\cs -> concat [parse (f a) cs' |
p <- parse p cs]) (a,cs')
The list comprehension used in the (>>=)
function
takes a bit of work to mentally parse. Let's break it down. Keep in mind
the type of this function, which is
Parser a -> (a -> Parser b) -> Parser b
.
instance Monad Parser where
return a = Parser (\cs -> [(a,cs)])
>>= f = Parser (\cs -> concat [parse (f a) cs' |
p <- parse p cs]) (a,cs')
p
is deconstructed to extract a
function of type String -> [(a,String)]
cs
to get
a tuple (a,cs')
of type (a,String)
instance Monad Parser where
return a = Parser (\cs -> [(a,cs)])
>>= f = Parser (\cs -> concat [parse (f a) cs' |
p <- parse p cs]) (a,cs')
f
, which has type
a -> Parser b
, is applied to the tuple's first element,
a
Parser b
is deconstructed via
parse
b
, of type
String -> [(b,String)]
is applied to the string
cs'
instance Monad Parser where
return a = Parser (\cs -> [(a,cs)])
>>= f = Parser (\cs -> concat [parse (f a) cs' |
p <- parse p cs]) (a,cs')
[(b,String)]
Now the fun part, switching from a list to a Maybe
as
defined above:
instance Monad Parser where
return a = Parser (\cs -> Just (a,cs))
>>= f = Parser (\cs -> case parse p cs of
p Nothing -> Nothing
Just (a,cs') -> parse (f a) cs')
This is a bit easier to parse in my head, and it is more apparent to
me both how the binding works and that the return type will be
Parser b
.
The rest of the changes are trivial, and in many cases no changes are needed at all.
class Monad m => MonadZero m where
zero :: m a
instance MonadZero Parser where
= Parser (\cs -> Nothing)
zero
class MonadZero m => MonadPlus m where
(++) :: m a -> m a -> m a
instance MonadPlus Parser where
++ q = Parser (\cs -> case parse p cs of
p Just (a,cs') -> Just (a,cs')
Nothing -> parse q cs)
string :: String -> Parser String
"" = return ""
string :cs) = do {char c; string cs; return (c:cs)} string (c