多項式函子

有一組有用的型別組合器可以用較小的組合來構建大型組合。這些作為 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 同構。這意味著 Kfmap 實現根本不做任何對映!

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

這種型別可以在 ProductData.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找到

用於通用程式設計的多項式仿函式

IK:*::+::.:可以被認為是某類簡單資料型別的構建塊的工具包。當你將它與固定點組合時,該套件變得特別強大,因為使用這些組合器構建的資料型別是 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