Background. In one of my classes we've been exploring the Parser
monad. The Parser
monad is typically defined as either
newtype Parser a = Parser (String -> [(a, String)])
Or as
newtype Parser a = Parser (String -> Maybe (a, String))
In either case, we can instance Parser
as a Functor
using code that works in both cases:
instance Functor Parser where
fmap f (Parser p) = Parser (fmap applyF . p)
where applyF (result, s) = (f result, s)
If we have a Parser
built to return Maybe (a, String)
, this applies f
to the result
if the result
exists. And if we have a Parser
built to return [(a, String)]
, this applies f
to each of the result
s returned in the list.
We can instance Applicative
, Monad
, MonadPlus
, and Alternative
is similarly generic ways (so that they work either for Maybe
or []
).
Question. If I parameterize Parser
based on the type used to wrap the result, how can I instance it for Functor
and friends?
newtype Parser m a = Parser (String -> m (a, String))
-- How do I instance `Parser` as a Functor if `m` is a Functor?
You can here construct a constraint that m
should be a type that is an instance of Functor
as well, and then fmap
on that result:
instance Functor m => Functor (Parser m) where
fmap f (Parser p) = Parser (\x -> fmap g (p x))
where g (r, s) = (f r, s)
Here g
is thus a function that performs the mapping f
on the first element of the tuple. We thus use that g
as a "mapping" function over the result.
This will thus work for any m
that is an instance of Functor
, like a Maybe
, a []
, a Tree
, etc.