Is this incremental parser a functor, if so how would `fmap` be implemented?

Question

I really hate asking this kind of question but I'm at the end of my wits here. I am writing an incremental parser but for some reason, just cannot figure out how to implement functor instance for it. Here's the code dump: Input Data Type Input is data type yielded by parser to the coroutine. It contains the current list of input chars being operated on by coroutine and end of line condition ``` data Input a = S [a] Bool deriving (Show) instance Functor Input where fmap g (S as x) = S (g <$> as) x ``` Output Data Type Output is data type yielded by coroutine to Parser. It is either a Failed message, Done [b], or Partial ([a] -> Output a b), where [a] is the current buffer passed back to the parser ``` data Output a b = Fail String | Done [b] | Partial ([a] -> Output a b) instance Functor (Output a) where fmap _ (Fail s) = Fail s fmap g (Done bs) = Done $ g <$> bs fmap g (Partial f) = Partial $ \as -> g <$> f as ``` The Parser The parser takes [a] and yields a buffer [a] to coroutine, w…

Accepted Answer

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!

Is this incremental parser a functor, if so how would `fmap` be implemented?

Solution

Problem