多项式函子

Created: November-22, 2018

有一组有用的类型组合器可以用较小的组合来构建大型组合。这些作为 Functor 的示例实例具有指导意义，它们也可用作泛型编程的技术，因为它们可用于表示一大类常见的仿函数。

身份仿函数

身份函子简单地包装了它的论点。它是来自 SKI 演算的 I 组合器的类型级实现。

newtype I a = I a

instance Functor I where
    fmap f (I x) = I (f x)

在 Data.Functor.Identity 模块中可以找到 I，名称为 Identity 。

恒定的算子

常量仿函数忽略其第二个参数，仅包含常量值。它是 const 的类型级模拟，是来自 SKI 演算的 K 组合子。

newtype K c a = K c

请注意，K c a 不包含任何 a 值; K () 与 Proxy 同构。这意味着 K 的 fmap 实现根本不做任何映射！

instance Functor (K c) where
    fmap _ (K c) = K c

K 也被称为 Const，来自 Data.Functor.Const 。

此示例中的其余仿函数将较小的仿函数组合成较大的仿函数。

Functor 产品

仿函数产品需要一对仿函数并将它们打包。它类似于一个元组，除了 (,) :: * -> * -> *在 types *上运行，(:*:) :: (* -> *) -> (* -> *) -> (* -> *) 在 functors * -> *上运行。

infixl 7 :*:
data (f :*: g) a = f a :*: g a

instance (Functor f, Functor g) => Functor (f :*: g) where
    fmap f (fx :*: gy) = fmap f fx :*: fmap f gy

这种类型可以在 Product 中的 Data.Functor.Product 模块中找到。

Functor 副产品

就像:*:类似于 (,) 一样，:+:是 Either 的仿函数级模拟。

infixl 6 :+:
data (f :+: g) a = InL (f a) | InR (g a)

instance (Functor f, Functor g) => Functor (f :+: g) where
    fmap f (InL fx) = InL (fmap f fx)
    fmap f (InR gy) = InR (fmap f gy)

:+:可以在 Data.Functor.Sum 模块中找到名称 Sum 。

Functor 组成

最后，:.:就像一个类型级别的 (.)，将一个仿函数输出并将其输入到另一个仿函数的输入中。

infixr 9 :.:
newtype (f :.: g) a = Cmp (f (g a))

instance (Functor f, Functor g) => Functor (f :.: g) where
    fmap f (Cmp fgx) = Cmp (fmap (fmap f) fgx)

Compose 型可以在 Data.Functor.Compose 中找到

用于通用编程的多项式仿函数

I，K，:*:，:+:和:.:可以被认为是某类简单数据类型的构建块的工具包。当你将它与固定点组合时，该套件变得特别强大，因为使用这些组合器构建的数据类型是 Functor 的自动实例。你可以使用该工具包构建模板类型，使用 I 标记递归点，然后将其插入 Fix 以获得可与标准动物园递归方案一起使用的类型。

名称	作为数据类型	使用仿函数套件
成对的值	`data Pair a = Pair a a`	`type Pair = I :*: I`
两个二个网格	`type Grid a = Pair (Pair a)`	`type Grid = Pair :.: Pair`
自然数	`data Nat = Zero \| Succ Nat`	`type Nat = Fix (K () :+: I)`
清单	`data List a = Nil \| Cons a (List a)`	`type List a = Fix (K () :+: K a :*: I)`
二叉树	`data Tree a = Leaf \| Node (Tree a) a (Tree a)`	`type Tree a = Fix (K () :+: I :: K a :: I)`
玫瑰树	`data Rose a = Rose a (List (Rose a))`	`type Rose a = Fix (K a :*: List :.: I)`

这种设计数据类型的工具包方法是通用编程库（如 generics-sop）背后的理念。我们的想法是使用如上所示的工具包编写泛型操作，然后使用类型类将任意数据类型转换为其通用表示形式：

class Generic a where
    type Rep a  -- a generic representation built using a kit
    to::a -> Rep a
    from::Rep a -> a