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, which yields back Output a b

data ParserI a b = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b }

Functor Implementation

It seems like all I have to do is fmap the function g onto the coroutine, like follows:

instance Functor (ParserI a) where
    fmap g p = PP $ \as k -> runPi p as (\xs -> fmap g $ k xs)

But it does not type check:

Couldn't match type `a1' with `b'
  `a1' is a rigid type variable bound by
       the type signature for
         fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b
       at Tests.hs:723:9
  `b' is a rigid type variable bound by
      the type signature for
        fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b
      at Tests.hs:723:9
Expected type: ParserI a b
  Actual type: ParserI a a1

Oh X( may I ask you to explain why? And how might I restructure it such that it is a functor? For example in Attoparsec.Incremental (depreicated), the coroutine has type similar to (c -> Input a -> Output a b), but I could not figure out what the c is there for — xiaolingxiao
fmap g p = PP $ \as k -> runPi p as (\xs -> fmap g $ k as) <- that last as there was intended to be an xs, wasn't it? — Daniel Fischer
Right. Now it makes sense (the error message). The problem is that you need to pass an Input a -> Output a b to runPi p as the second argument. But what you have, k, is an Input a -> Output a c (when g's type is b -> c). You'd need some way to convert an Input a -> Output a c into an Input a -> Output a b. But you have nothing to create a b from a c. The type variable b occurs in a wrong position for ParserI to be made a Functor. That's what Philip JF said. — Daniel Fischer
Do you definitely need the second argument to the PP constructor to be a function, or could you store that information some other way? This is clearly where the problem lies. — AndrewC

J. Abrahamson J. Abrahamson · Accepted Answer · 2013-07-19T04:57:05

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 Functors 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 Difunctors 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. Profunctors 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?

1 Answers