As Philip JF declared, it's not possible to have an instance Functor (ParserI a)
. The proof goes by variance of functors—any (mathematical) functor must, for each of its arguments, be either covariant or contravariant. Normal Haskell Functor
s are always covariant which is why
fmap :: (a -> b) -> (f a -> f b)`
Haskell Contravariant
functors have the similar
contramap :: (b -> a) -> (f a -> f b)`
In your case, the b
index in ParserI a b
would have to be both covariant and contravariant. The quick way of figuring this out is to relate covariant positions to +
and contravariant to -
and build from some basic rules.
Covariant positions are function results, contravariant are function inputs. So a type mapping like type Func1 a b c = (a, b) -> c
has a ~ -
, b ~ -
, and c ~ +
. If you have functions in output positions, you multiply all of the argument variances by +1
. If you have functions in input positions you multiply all the variances by -1
. Thus
type Func2 a b c = a -> (b -> c)
has the same variances as Func1
but
type Func3 a b c = (a -> b) -> c
has a ~ 1
, b ~ -1
, and c ~ 1
. Using these rules you can pretty quickly see that Output
has variances like Output - +
and then ParserI
uses Output
in both negative and positive positions, thus it can't be a straight up Functor
.
But there are generalizations like Contravariant
. The particular generalization of interest is Profunctor
(or Difunctor
s which you see sometimes) which goes like so
class Profunctor f where
promap :: (a' -> a) -> (b -> b') -> (f a b -> f a' b')
the quintessential example of which being (->)
instance Profunctor (->) where
promap f g orig = g . orig . f
i.e. it "extends" the function both after (like a usual Functor
) and before. Profunctor
s f
are thus always mathematical functors of arity 2 with variance signature f - +
.
So, by generalizing your ParserI
slightly, letting there be an extra parameter to split the ouput types in half, we can make it a Profunctor
.
data ParserIC a b b' = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b' }
instance Profunctor (ParserIC a) where
promap before after (PP pi) =
PP $ \as k -> fmap after $ pi as (fmap before . k)
and then you can wrap it up
type ParserI a b = ParserIC a b b
and provide a slightly less convenient mapping function over b
mapPi :: (c -> b) -> (b -> c) -> ParserI a b -> ParserI a c
mapPi = promap
which really drives home the burden of having the variances go both ways---you need to have bidirectional maps!