这个增量解析器是否是一个函数对象，如果是，`fmap`应该如何实现？

Question

这个增量解析器是否是一个函数对象，如果是，`fmap`应该如何实现？

5

我很不情愿地提出这种问题，但我已经快要放弃了。我正在编写一个增量解析器，但是由于某些原因，无法理解如何为其实现函数对象实例。以下是代码转储： 输入数据类型 输入是由解析器生成的数据类型，用于协程。它包含当前列表中协程正在操作的输入字符及行末条件。

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

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

输出数据类型

输出数据类型是协程传递给解析器的数据类型。它可以是失败的消息、完成的 [b] 或部分的 ([a] -> Output 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] 以供协程使用，协程会返回输出 Output 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

- xiaolingxiao

哦，X（），能否请您解释一下为什么？我该如何重构它以使其成为一个函数对象？例如，在 Attoparsec.Incremental（已弃用）中，协程的类型类似于（c -> Input a -> Output a b），但我无法弄清楚 c 在那里的作用。 - xiaolingxiao

fmap g p = PP $ \as k -> runPi p as (\xs -> fmap g $ k xs) <- 那个最后的 as 应该是想写成 xs，对吧？ - Daniel Fischer

@DanielFischer 是的，我已经修复了它并解决了相关的错误信息。谢谢！ - xiaolingxiao

2

好的，现在错误信息有意义了。问题是您需要将“Input a -> Output a b”作为第二个参数传递给“runPi p”。但是您拥有的是“k”，它是一个“Input a -> Output a c”（当“g”的类型为“b -> c”时）。您需要一种方法将“Input a -> Output a c”转换为“Input a -> Output a b”。但是您没有任何方法从“c”中创建“b”。类型变量“b”出现在错误的位置上，无法使“ParserI”成为“Functor”。这就是Philip JF所说的。 - Daniel Fischer

1

你是否一定需要PP构造函数的第二个参数是一个函数，或者你可以以其他方式存储这些信息？显然这就是问题所在。 - AndrewC

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- J. Abrahamson · Accepted Answer

正如Philip JF所说，不可能有一个instance Functor (ParserI a)。这个证明涉及到函子的变异性——任何（数学上的）函子都必须对于它的每个参数是协变的还是逆变的。普通的HaskellFunctor总是协变的，这就是为什么。

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

Haskell Contravariant 函子与其它类型函子类似

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，因此它不能是一个简单的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 f 因此始终是具有变量签名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

这真正强调了双向映射的重要性，因为方差需要在两个方向上变化！