haskell - 两个仿函数的组合是仿函数

Question

在 a previous answer , Petr Pudlak 定义了 CFunctor类，用于除从 Hask 到 Hask 之外的仿函数。使用类型族重新编写它，它看起来像

class CFunctor f where
  type Dom f :: * -> * -> *               -- domain category
  type Cod f :: * -> * -> *               -- codomain category
  cmap :: Dom f a b -> Cod f (f a) (f b)  -- map morphisms across categories

看起来像的实例，例如

instance CFunctor Maybe where
  type Dom Maybe = (->)                   -- domain is Hask
  type Cod Maybe = (->)                   -- codomain is also Hask 
  cmap f = \m -> case m of
                   Nothing -> Nothing
                   Just x  -> Just (f x)

在范畴论中，只要 F : C --> D 是仿函数且 G : D --> E 是仿函数，则组合 GF : C --> E 也是仿函数。

我想用 Haskell 来表达这一点。因为我不会写 instance CFunctor (f . g)我介绍一个包装类:

newtype Wrap g f a = Wrap { unWrap :: g (f a) }

在写 CFunctor例如我得到的

instance (CFunctor f, CFunctor g, Cod f ~ Dom g) => CFunctor (Wrap g f) where
  type Dom (Wrap g f) = Dom f
  type Cod (Wrap g f) = Cod g
  cmap = undefined

但我不知道 cmap 的实现是什么应该。有什么建议吗？

PS 这一切的最终原因是还要引入一个类 Adjunction使用方法 unit和 counit ，然后自动从附加词中派生出 monad 实例。但首先，我需要向编译器展示两个仿函数的组合也是一个仿函数。

我知道我可以使用 cmap.cmap在 g (f a) 类型的对象上这会起作用，但它看起来有点像作弊 - 肯定仿函数只是一个仿函数，编译器不应该知道它实际上是另外两个仿函数的组合？

Answer 1

给定仿函数 F : C → D和 G : D → E , 一个仿函数组合 G ∘ F : C → E是类别之间的对象映射C和 E ，这样 (G ∘ F)(X) = G(F(X))以及态射之间的映射，使得 (G ∘ F)(f) = G(F(f)) .

这表明您的 CFunctor实例应定义如下:

instance (CFunctor f, CFunctor g, Cod f ~ Dom g) => CFunctor (Wrap g f) where
  type Dom (Wrap g f) = Dom f
  type Cod (Wrap g f) = Cod g
  cmap f = cmap (cmap f)

但是，组成 cmap两次给你 Dom f a b -> Cod g (g (f a)) (g (f b))和 cmap在这种情况下，类型为 Dom f a b -> Cod g (Wrap g f a) (Wrap g f b) .

我们可以从 g (f a)至 Wrap g f反之亦然，但由于实例声明没有对 Cod g 的结构做出任何假设，我们运气不好。

由于我们知道仿函数是类别之间的映射，我们可以使用 Cod g是 Category (在 Haskell 方面，这需要 Category (Cod g) 约束)，这给了我们很少的操作:

cmap f = lift? unWrap >>> cmap (cmap f) >>> lift? Wrap

然而，这需要一个方便的起重运算符(operator) lift? ，它从 Hask 中提升一个函数分类到 Cod g类别。写作 Cod g如 (~>) , lift? 的类型一定是:

lift? :: (a -> b) -> (a ~> b)

lift? unWrap  :: Wrap g f a ~> g (f a)
cmap (cmap f) :: g (f a)    ~> g (f b)
lift? Wrap    :: g (f b)    ~> Wrap g f b

lift? unWrap >>> cmap (cmap f) >>> lift? Wrap :: Wrap g f a ~> Wrap g f b

现在，这个起重运算符(operator)至少有两种选择:

您可以从 Category (Cod g) 扩展约束至Arrow (Cod g)在这种情况下，起重运算符(operator)变为 arr ,

或者，正如 Sjoerd Visscher 在评论中提到的那样，您可以使用 Wrap 的事实。和 unWrap在语义上是 id在运行时，在这种情况下使用 unsafeCoerce是有道理的。