两个仿函数的组成是一个仿函数

Question

在之前的回答中,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,然后自动从adjunctions派生单子实例.但首先,我需要向编译器显示两个仿函数的组合也是一个仿函数.

我知道我可以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,我们的运气了.

既然我们知道functor是类别之间的映射,我们可以使用的事实Cod g是Category(在Haskell方面,这需要一个Category (Cod g)约束),这给我们很少的操作:

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

然而,这需要方便的提升操作器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

现在,这个提升操作员至少有两种选择:

• 你可以扩展constrait Category (Cod g),Arrow (Cod g)在这种情况下,提升操作员arr,
• 或者,正如Sjoerd Visscher在评论中提到的那样,你可以在运行时使用Wrap并且unWrap在语义id上的事实,在这种情况下,使用unsafeCoerce是合理的.