在某种意义上，“Fix”和“(,)”可以被视为函子吗？

Question

我一直想知道一个完整的、包罗万象的背景instance Functor (f :.: g)是什么样的。我脑海中立即浮现的想法是：

newtype (f :.: g) a = Comp (f (g a))
instance (Functor f, Functor g) => Functor (f :.: g) where
    fmap f (Comp x) = Comp (fmap (fmap f) x)

但是，两个逆变函子也会组合成协变的，如下所示：

instance (Contravariant f, Contravariant g) => Functor (f :.: g) where
    fmap f (Comp x) = Comp (contramap (contramap f) x)

这已经不是一个有希望的开始。然而，我也注意到，从技术上讲，f甚至g不必有 kind * -> *—— 唯一的要求f :.: g :: * -> *就是 thatf :: k -> *和g :: * -> ksome k. 这意味着非函子类型可以组成函子，例如

newtype Fix f = Fix (f (Fix f))
instance Functor (Fix :.: (,)) where
    fmap f (Comp x) = Comp (go x) where
        go (Fix (x,xs)) = Fix (f x,go xs)

Fix :.: (,)与以下类型同构Stream：

data Stream a = a :> Stream a

所以这似乎确实是一个不平凡的问题。这让我开始思考——如果 Haskell 的Functor类型类代表从 Hask 到 Hask 的分类函子，这是否意味着像Fix和一样的类型(,)可以是作用于其他类别的函子？这些类别是什么？

Answer 1

是的，我们可以从构造函数的形状中准确地读出它的含义。我们(,)先来看一下。

\n

函(,)子

\n

(,) :: * -> * -> *\n

\n

这需要两种类型并产生一种类型。直到同构，这相当于

\n

(,) :: (*, *) -> *\n

\n

即我们也可以取消函数的柯里化并同时获取两个参数。因此(,)可以将其视为Hask \xc3\x97 Haskto 的函子Hask，其中Hask \xc3\x97 Hask是产品类别。我们有一个词来表示函子，其域是两个类别的乘积。我们称之为 bifunctor ，它实际上base是在Haskell中。具体来说，双函子p能够将产品类别中从(a, b)到 的映射转换为从到 的映射。Haskell 的类型类以稍微不同但等效的方式编写此内容(a\', b\')p a bp a\' b\'

\n

bimap :: Bifunctor p => (a -> b) -> (c -> d) -> p a c -> p b d\n

\n

有图有a -> b图，就完全等同于在产品类别中c -> d有图。（我的意思是：产品类别中的地图被定义为地图和的产品）。(a, c) -> (b, d) (a, c) -> (b, d)a -> bc -> d

\n

函Fix子

\n

Fix我们也可以用同样的方法来处理。

\n

newtype Fix f = Fix (f (Fix f))\n

\n

它的形状是

\n

Fix :: (* -> *) -> *\n

\n

它采用单参数类型构造函数并生成一种类型。

\n

现在，在 Haskell 中，该* -> *部分可以是任何单参数类型构造函数，但绝对使用函子要好得多。因此，我将设置稍微更强的约束（事实证明我们很快就会需要），即 的参数* -> *是Fixa ，即来自to 的Functor函子。HaskHask

\n

在这种情况下，Fix具有成为从函子类别 Hask ^ Hask到类别 的函子的正确形状Hask。明确地说，函子将对象与对象、箭头与箭头联系起来。因此，让我们一次一步地迈出这一步。

\n

对象部分很简单，我们已经定义了它。具体来说，Fix采用函子f（函子是函子类别的对象；如果还没有意义，请再次阅读）并将其映射到Fix f我们刚刚定义的类型。

\n

现在，函子范畴的箭头是自然变换。给定两个函子，从到 的f, g :: C -> D自然变换是从 的对象到的箭头的映射。具体来说，对于类别 中的每个对象，应该是一个从 到 的箭头，具有以下一致性条件：\xce\xb1fgCDxC\xce\xb1 xDf xg x

\n

\n

对于h : x -> y中的每个箭头C，我们必须有(g h) . (\xce\xb1 x) === (\xce\xb1 y) . (f h)

\n

\n

（以真正的范畴论精神，非常宽松地使用诸如函数组合之类的符号）

\n

绘制为交换图，以下必须交换，

\n

\n

Haskell 实际上并没有用于自然转换的内置类型。使用Rank-N类型，我们可以写出正确的形状

\n

(forall a. f a -> g a)\n

\n

这是自然变换的形状，但当然我们还没有验证相干性。所以我们只需要相信它满足该属性。

\n

考虑到所有这些抽象的废话，如果Fix是 from Hask ^ Haskto的函子Hask，它应该自然转换为普通的 Haskell 函数，并且应该具有以下形状。

\n

fixmap :: (Functor f, Functor g) => (forall a. f a -> g a) -> Fix f -> Fix g\n

\n

一旦我们有了这种类型，我们就可以相当容易地编写实现。

\n

fixmap h (Fix inner) = Fix (h . fmap (fixmap h) $ inner)\n

\n

或者，等价地（根据自然变换的规则），

\n

fixmap h (Fix inner) = Fix (fmap (fixmap h) . h $ inner)\n

\n

我不知道这种函子形状的惯用名称，也不知道包含它的类型类，但当然没有什么可以阻止您自己制作它。

\n