4 ms·
So, for an interesting example of using monads, consider parser combinators. I'm basing this loosely off of the parsers provided by the parsec package, but sim
by dllthomas 12y ago
So, for an interesting example of using monads, consider parser combinators. I'm basing this loosely off of the parsers provided by the parsec package, but simplifying a bit.
Let the type "Parser a" represent a parser that produces an "a", after consuming some (or no) input.
(In Haskell, lowercase letters are used for polymorphic types; Parser Integer is a parser that produces an Integer, Parser String a parser that produces a string, and so on. Any concrete value will be of some more specialized type, but functions can work on the polymorphic version if they don't rely on it being something more specific.)
Note that parsers may also fail, and give up on parsing further input, instead returning information about how it failed.
To run a parser against some input, we can do something like:
case (parse someParser inputString) of
ResultFailure errorString -> do something with error string
ResultSuccess value -> do something with value
where
parse :: Parser a -> String -> Result a
data Result a = ResultFailure String | ResultSuccess a
We can put together a lot of things of this type. The simplest returns just a fixed thing and doesn't even look at the input.
return :: a -> Parser a
So the expression,
parse (return 5) inputString
would reduce to ResultSuccess 5, regardless of the input.
We can also have things that return the next character, whatever it is:
anyChar :: Parser Char
parse anyChar "f" -- ResultSuccess 'f'
parse anyChar "7" -- ResultSuccess '7'
parse anyChar "" -- ResultFailure "premature end of input"
Or we can have something more restricted, like...
oneOf :: [Char] -> Parser Char
abc = oneOf ['a', 'b', 'c']
parse abc "a" -- ResultSuccess 'a'
parse abc "d" -- ResultFailure "unexpected 'd'"
And we can have more sophisticated things:
natural :: Parser Integer
So now... where does "monad" come in?
Well, when we go to build a new parser out of these components, we need some way of combining them. We can do our parsing explicitly...
parseWithLeftovers :: Parser a -> String -> (String, Result a)
parseTwoIntegers input = case parseWithLeftovers integer input of
(_, ResultFailure errorString) -> ...
(input2, ResultSuccess int1) -> case parseWithLeftovers whiteSpace input2 of
(_, ResultFailure errorString) -> ...
(input3, ResultSuccess _) -> case parseWithLeftovers integer input3 of
(_, ResultFailure errorString) -> ...
(_, ResultSuccess int2) -> return (int, int2)
It should be plenty obvious why we don't want to do that every time. Let's factor out the boiler plate. The question is what that looks like...
What if we set it up so those results could be collected and passed to an arbitrary function? That could let us write something like...
parseTwoIntegers = (,) <$> integer <*> (whiteSpace *> integer)
While you may not understand the symbols, I expect you'll agree that's quite a bit more readable.
But that still doesn't actually require monads. <$> is a synonym for fmap, the two operators containing asterisks are from Applicative. Can we do everything we might want with these, without getting crazy explicit and chaining parsers by hand again?
Well, let's look a little closer at what's going on above. Specialized for clarity, the above operators have the following types:
(,) :: a -> b -> (a, b)
tuple operator - takes two arguments, makes a tuple out of them
(<$>) :: (a -> b) -> Parser a -> Parser b
"fmap" - applies a function to the result of a
parser, making it into a parser that does the
same thing but returns the modified result
(<*>) :: Parser (a -> b) -> Parser a -> Parser b
"ap" - takes a parser *producing a function*, and a
parser producing a value, and gives us a parser
that applies the function to the value
(*>) :: Parser a -> Parser b -> Parser b
Takes two parsers, runs both, returns the result of the second
Walking the above expression from left to right, we see...
(,) :: a -> b -> (a, b) -- tuple operator
(,) <$> :: Parser a -> Parser (b -> (a, b))
note that the partial application of (,) *inside*
the parser gives us a parser returning a function
(,) <$> integer :: Parser (b -> (Integer, b))
we've picked our "a" and are left with a parser
returning a function - a job for "ap"
(,) <$> integer <*> :: Parser b -> Parser (Integer, b)
It should be reasonably apparent how the bit in
parens reduces, so skipping ahead...
(,) <$> integer <*> (whiteSpace *> integer) :: Parser (Integer, Integer)
It's easier - and not wrong - to think of "f <$> ... <> ... <> ..." as "apply this function to these wrapped values, giving me a wrapped result" - but the above is how that happens, and following it is a bit necessary for this next bit...
What if we want to write
readNChars :: Parser [Char]
where the parser first reads the number of characters to read, and then reads that number of characters?
Looking at the above operators, there's something that the function arguments (wrapped or not) have in common: none of the function arguments return a Parser. So the functions can't dictate what is parsed. That's what we fix next:
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
"bind" - takes a parser, and a function that
returns a parser, runs the first parser, feeds the
result into the function, and runs the resulting
parser
This, then, allows us to say things like:
parseCountItems :: Parser a -> Integer -> Parser [a]
parseCountItems p i = sequence (genericReplicate i p)
readNChars :: Parser [Char]
readNChars = integer >>= parseCountItems anyChar
Haskell programmers care that it's a monad for three reasons. First, communicative value - the pattern comes up a lot and it's useful to be able to quickly convey what's going on. Second, there are actually a number of useful functions that can be applied to any monad. For instance,
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
when :: Monad m => Bool -> m () -> m ()
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
Finally, do notation. Haskell provides some syntactic sugar that turns
do
statement1
var <- statement2
statement3 var
into
statement1 >>= \ _ -> statement2 >>= \ var -> statement3 var
The above "readNChars" could be rewritten:
readNChars = do
cnt <- integer
sequence (genericReplicate cnt anyChar)
Do notation can often be clearer for complicated monadic expressions.