多項式函子

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