parsing - 这个增量解析器是仿函数吗？如果是的话， `fmap` 将如何实现？

Question

我真的很讨厌问这种问题，但我已经无计可施了。我正在编写一个增量解析器，但由于某种原因，只是无法弄清楚如何为其实现仿函数实例。这是代码转储:

输入数据类型

输入是解析器向协程生成的数据类型。它包含协程正在操作的当前输入字符列表和行结束条件

data Input a = S [a] Bool deriving (Show)

instance Functor Input where
    fmap g (S as x) = S (g <$> as) x

输出数据类型

输出是协程向解析器生成的数据类型。它可以是失败消息、完成 [b] 或部分([a] -> 输出 a b)，其中 [a] 是传回解析器的当前缓冲区

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

解析器

解析器接受 [a] 并为协程生成一个缓冲区 [a]，该缓冲区返回输出 a b

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

仿函数实现

看来我所要做的就是将函数 g fmap 到协程上，如下所示:

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

但它没有类型检查:

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

Answer 1

正如 Philip JF 所声明的那样，不可能有实例 Functor (ParserI a)。证明是通过仿函数的方差来进行的——任何(数学)仿函数对于它的每个参数都必须是协变的或逆变的。正常的 Haskell Functor 总是协变的，这就是为什么

fmap :: (a -> b) -> (f a -> f b)`

haskell Contravariant functors有类似的

contramap :: (b -> a) -> (f a -> f b)`

在您的情况下，ParserI a b 中的 b 索引必须同时是协变和逆变的。解决这个问题的快速方法是将协变位置与 + 相关联，将逆变位置与 - 相关联，并根据一些基本规则进行构建。

协变位置是函数结果，逆变位置是函数输入。因此，像 type Func1 a b c = (a, b) -> c 这样的类型映射具有 a ~ -、b ~ - 和 >c~+。如果输出位置有函数，则将所有参数方差乘以+1。如果您在输入位置有函数，则将所有方差乘以-1。因此

type Func2 a b c = a -> (b -> c)

与 Func1 具有相同的差异，但是

type Func3 a b c = (a -> b) -> c

有a ~ 1、b ~ -1和c ~ 1。使用这些规则，您可以很快看到 Output 具有诸如 Output - + 之类的差异，然后 ParserI 使用 Output负数和正数位置，因此它不能是直接的仿函数。

<小时/>

但是也有像逆变这样的概括。兴趣的具体概括是 Profunctor (或者你有时会看到的Difunctor)，就像这样

class Profunctor f where
  promap :: (a' -> a) -> (b -> b') -> (f a b -> f a' b')

典型的例子是(->)

instance Profunctor (->) where
  promap f g orig = g . orig . f

即它在之后(就像通常的 Functor )和之前“扩展”了函数。因此，Profunctor 的 f 始终是具有方差签名 f - + 的 arity 2 数学仿函数。

因此，通过稍微概括您的 ParserI，让有一个额外的参数将输出类型分成两半，我们可以使其成为 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)

然后你就可以把它包起来

type ParserI a b = ParserIC a b b

并在b上提供稍微不太方便的映射函数

mapPi :: (c -> b) -> (b -> c) -> ParserI a b -> ParserI a c
mapPi = promap

这确实让我们明白了双向差异带来的负担——你需要有双向 map !