5

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

输入数据类型

输入是解析器向协程产生的数据类型。它包含由协程和行尾条件操作的当前输入字符列表

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

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

输出数据类型

输出是协程向 Parser 产生的数据类型。它可以是 Failed 消息、Done [b] 或 Partial ([a] -> Output ab)，其中 [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] 给协程，协程返回输出 ab

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

函子实现

似乎我所要做的就是将函数 g 映射到协程上，如下所示：

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
4

1 回答 1

11

正如 Philip JF 所说，不可能拥有instance Functor (ParserI a). 证明是通过函子的方差进行的——任何（数学）函子对于它的每个参数都必须是协变的或逆变的。正常的 HaskellFunctor总是协变的，这就是为什么

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

HaskellContravariant函子有类似的

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

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

协变位置是函数结果，逆变是函数输入。因此，像type Func1 a b c = (a, b) -> chas 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，因此它不可能是直线上升Functor。

但也有类似的概括Contravariant。感兴趣的特定概括是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因此， sf始终是具有方差签名的 arity 2 的数学函子f - +。

因此，通过稍微概括一下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

这真的让你背负着双向变化的负担——你需要有双向地图！

于 2013-07-19T04:57:05.523 回答