前言

為了能夠不拖更，我決定討論一些小一點的話題，本章中我們將討論基本函子（base functor）這一概念，以及 recursion-schemes 庫函數中如何使用基本函子來使 recursion scheme 在實踐中更為優雅高效。

前情回顧

在之前數篇文章中，我們已經看到了某種定義參數化數據類型的模式，我們從這樣的數據類型定義：

data Expr
= Index Expr Expr
| Call Expr [Expr]
| Unary String Expr
| Binary Expr String Expr
| Paren Expr
| Literal Int
deriving (Show, Eq)


變為了這樣：

data ExprF a
= Index a a
| Call a [a]
| Unary String a
| Binary a String a
| Paren a
| Literal Int
deriving (Show, Eq, Functor)


一樣的數據類型，但是 kind [1] 變為了 * -> *，所有的 Expr 都用 a 做了替換。接著我們使用了 Y-組合子的技巧來定義 Term，這樣的定義與之前的 Expr 等價，但是可以使用 fmap，以及 cata：

newtype Term f = In { out :: f (Term f) }

type Expr = ExprF (Term ExprF)

類似地，在第四章中，我們定義了自然數，它的 kind 也是 * -> * 的：

data Nat a
= Zero
| Next a
deriving Functor


我們也定義了 Plant，也是類似的定義：

data Plant a
= Root a
| Stalk a
| Fork a a a
| Bloom


這個表達數據的辦法確實清晰明瞭，但是也有相應的問題。

假設我們考慮一個最簡單地鏈表類型：a:[a]。

infixr 5 :
data [] a = a : [a]
| []


顯然 cata，我們最基本的右摺疊操作，應該可以支持這一結構。畢竟它的 kind 也是 * -> *。但如果我在這一結構上使用 Term，我們馬上就遇到了麻煩：我們無法在了鏈表裡存儲元素了。 a 只能表示嵌套的 Term a 這一結構。沒有地方來存儲鏈表本身的元素。可以想見，這樣的鏈表並不十分有用。

當然我們也可以將 [a] 轉換為之前我們常見的那種模式，新加入一個參數來表達遞歸的部分。

data ListF a b
= Cons a b
| Nil
deriving (Show, Eq, Functor)


在這樣的結構上我們就可以完成遞歸了：

listSum :: Num a => Algebra (ListF a) a
listSum (Cons a b) = a + b
listSum Nil = 0


但是這一辦法非常醜陋，如果對於 []，這樣的類型全部進行手動替換的話，我們完全喪失了使用 recursion scheme 的初衷。幸好並不是我一個人這麼覺得，實際上有非常多種做法來繞開這個問題，我們會著重描述 recursion-schemes 中解決該問題的辦法。

救星基本函子

recursion-schemes 庫文檔中有如下定義：

type family Base t :: * -> *


這個定義明顯會嚇到不少人，但實際上並沒有那麼難以理解，而正是這一定義使得 recursion-schemes 在易用性上遠遠超越了它的競爭對手們。

Base 類型類的目的就是將 Haskell 中的原生類型定義，或者我們自己的類型定義與相對應的參數化類型定義綁定起來。對 type family 的詳盡用法進行介紹顯然超出了本文的範疇（感興趣的讀者可參閱 GHC wiki），我們可以簡單認為 type family 是一個在類型上定義函數的方式。如果我們定義了一個 type family，以及一個它的實例（這與 typeclass 以及它的實例實際上是類似的）：

type family Something t

type instance Something Foo = Bar

那麼之後我們無論在哪裡遇到調用 Something Foo，GHC 類型系統都會將它代換為 Bar，為什麼不直接寫 Bar 呢？—— 這初看起來無關緊要，但這為我們建立兩種類型間的聯繫提供了便利。

我們觀察一下 Base 的定義，當你傳入 t 時，你得到了一個 * -> * 的類型，回想一下不難發現，我們也把 Expr 變成 ExprF 的過程也是一個 * 到 * -> * 的過程。同理，list 就是一個 * -> * 到 * -> * -> * 的過程。

一個 Base 類型的實例或許更能說明問題：

type instance Base [a] = ListF a


簡單來說，這樣的寫法使得 ListF a 可以用 Base [a] 來表達。對應於每種類型，它的參數化遞歸類型（* 變換為 * -> *）只有一種合法實現，對應來看，對於任意 a，Base a 也只有一種合法實現。

當我們把這一定義與 Recursive 類型類相結合以後，事情變得有趣起來。（為了闡述方便，這裡的定義進行了適當簡化）。

class (Functor (Base t)) => Recursive t where
project :: t -> Base t t
cata :: (Base t a -> a) -> t -> a


Recursive 類型類與 Foldable 類型類實際上是同構的[2]。無論我們定義了怎樣的 Recursive 實例，Expr 或是 [a]，我們都可以在上面做摺疊操作。實際上這裡我們定義了兩種方法，project 參數為一個 t 類型變數，得到變化後的 Base 形式。以及 cata 函數，給定一個 Base t a -> a 函數，一個初始化的 t，最後得到一個 a。

這裡的 cata 和我們之前的定義初看上去似乎有所不同。我們定義的 cata 只有 Founctor 的約束：

cata :: (Functor f) => Algebra f a -> Term f -> a
cata f = out >>> fmap (cata f) >>> f


但我們的 cata 必須使用 Term List 而不是簡單的 [a]，而使用 Recursive 類型類允許我們向 cata 傳入一般的數據類型 t 而不是 Term t，Recursive 的實例使用 project 函數來將提供的類型轉換為帶參數的類型，並將它傳遞給 cata 函數，省去了我們包裝 Term 和拼接 Cons 的工作。

sumList :: Num a => [a] -> a
sumList = cata go where
go Nil = 0
go (Cons a acc) = a + acc


Recursive 的魔法不止於此，根據它的最小編譯指示，我們實現 Recursive 類時，最低限度只需要實現 project 函數即可。cata 等函數可以沿用默認定義。

class Functor (Base t) => Recursive t where
project :: t -> Base t t

cata :: (Base t a -> a) -- ^ a (Base t)-algebra
-> t -- ^ fixed point
-> a -- ^ result
cata f = c where c = f . fmap c . project

這只是 cata 的默認實現而已，如果在你特定的數據結構上，cata 存在更好的實現，當然你可以重寫這一定

Recursive 類型類中還定義了其他方法，例如我們曾在之前的文章中討論過的 para，還包括一些我們沒涉及的比如泛化的 paramorphism gpara，以及 Fokkinga 提出的 prepromorphism prepro，或許我們會在之後的文章中討論它們（譯者註：作者在之後的文章中並未討論它們，或許我會在之後的文章中討論它們？）。

注意 Base 類型受限於 Recursive 實例：t 必須有一個 Base 的實例，而且 Base t 必須是一個 Functor 類型，這是因為 cata 依賴於使用 fmap 在進行遞歸操作。

正是因為有了 Recursive 類型類，我們可以操作 [a] 而非 ListF，Expr 而非 ExprF，我們可以在簡單數據類型上使用 Recursion Scheme。這一技巧在其它的庫中也有採用，比如 José Pedro Magalh?es 的 regular。

下面我們看一下定義 [a] 為 Recursive 的實例。[] 變為了 Nil，: 變為了 Cons。

instance Recursive [a] where
project (x:xs) = Cons x xs
project [] = Nil


另外一個重要的例子是 Natural —— 我們在之前也討論過。我們自己定義了自然數類型 Nat，這一類型與 Maybe 等同的。所以在 recursion-schemes 中就使用了 Maybe 來實現 Natural 的 Recursive 和 Base。

type instance Base Natural = Maybe

instance Recursive Natural where
project 0 = Nothing
project n = Just (n - 1)

更進一步

正如我們之前所看到的，給定一個 t，構造 Base 的示例是非常直觀的：為原來的類型定義加入一個新的類型變數，接著改造每一個構造函數使其可以加入遞歸的新的類型變數。而藉助 Haskell 的模板能力，recursion-schemes 可以生成如下的代碼：

import Data.Functor.Foldable.TH

data Expr
= Index Expr Expr
| Call Expr [Expr]
| Unary String Expr
| Binary Expr String Expr
| Paren Expr
| Literal Lit
deriving (Show, Eq)

makeBaseFunctor Expr

其中 makeBaseFunctor 生成的代碼實際上等價於：

data ExprF a
= IndexF a a
| CallF a [a]
| UnaryF String a
| BinaryF a String a
| ParenF a
| LiteralF Lit
deriving (Show, Eq, Functor)

type instance Base Expr = ExprF

instance Recursive Expr where
project (Index a b) = IndexF a b
project (Call a b) = CallF a b
-- and so on and so forth

這實際上就是講上述描述應用而生成的代碼，為了避免命名衝突，新的類型構造函數帶一個後綴 『F』（中綴表達式後綴為『$』）。

應用了 Haskell 模板以後，意味著對於我們這些庫使用者，使用 recursion-schemes 的代價非常之小。而這些處理嵌套結構的能力，在我編寫 Haskell 生產級別代碼時帶來了非常大的益處。你可以非常優雅地處理嵌套結構，不需要引入任何額外代碼。

再次翻轉箭頭

在之前的文章中，我們多次使用翻轉箭頭的操作來生成展開操作。所以想必讀者們對於我們要進行的操作也不會陌生，我們會同樣對 Recursive 進行類似操作。從而得到 Corecursive 類型類，對應相應的展開操作。

class Functor (Base t) => Corecursive t where
embed :: Base t t -> t
ana :: (a -> Base t a) -> a -> t


我們已經展示過，從 cata 生成 ana 的過程，所以只剩下通過翻轉箭頭從 project 生成 embed 的過程，我們從 Base 函子生成 t。

也對應於 cata，ana 使用 fmap 和 embed 生成：

class Functor (Base t) => Corecursive t where
embed :: Base t t -> t
ana
:: (a -> Base t a) -- ^ a (Base t)-coalgebra
-> a -- ^ seed
-> t -- ^ resulting fixed point
ana g = a where a = embed . fmap a . g


embed 實例的定義也是非常直觀的對稱：

instance Corecursive [a] where
embed (Cons x xs) = x:xs
embed Nil = []


更棒的是，實際上你不必真的自己寫 Corecursive 的實例，makeBaseFunctor 會同時自動生成 Recursive 和 Corecursive 的實例。

餐後甜點

敏銳的讀者可能已經注意到了，recursion-schemes 庫中的 cata 實現與我們之前的形式有一些微妙的不同。我們的定義中，包括 cata 的柯里化—— cata f，將它傳給了 fmap：

cata :: (Functor f) => Algebra f a -> Term f -> a
cata f = out >>> fmap (cata f) >>> f


而 recursion-schemes 則實現了 where 語句定義了變數 c 來代換 cata f。

兩種 cata 定義都是 point-free 的，但是 recursion-schemes 的實現曾令筆者十分困惑，c 的出現似乎毫無意義。直到若干年以後，我才大致理解了其中的含義。如果你避免了這樣的柯里化，GHC 會生成更加高效的代碼。柯里化函數必須攜帶它們的參數，在調用過程中必須追溯這些參數。而對於一個裸函數，調用的過程會簡單得多（你可以訪問 GHC 的 wiki 頁面 heap objects 來獲得更多噁心的細節）。

當得知這一知識以後，我們就可以發現 cata 的實現十分優雅，通過 cata 的命名，我們可以像一個普通函數一樣對待它，從而生成更加高效的代碼。一般來說這樣的優化，效果是微乎其微的，但是由於 cata 在每層摺疊操作中都會被調用，累積導致的效率損失對於一個庫函數來說也是不可忽視的。

結語

我必須向 Edward Kmett 表示感謝，他的 recursion-schemes 庫優雅且富有啟發性。同時我還要感謝 Austin Seipp，幫我檢查了文章關於 GHC 代碼生成部分的描述。

我希望能在下一篇文章中介紹 hylomorphisms and chronomorphisms，從而可以結束這一系列文章。感謝大家的耐心閱讀！

[1]: 如果你對 kind 這一定義並不熟悉，你可以大致地認為，kind 描述了數據類型需要的參數個數，Expr 中不需要參數，所以 kind 為 *，需要一個參數的則為 * -> *。需要更多參數的比如 Either，kind 為 * -> * -> *，對於 kind 更精準的描述是類型的類型，但是我們可以簡單地將其理解為參數的個數表示。對於任意類型，在 GHCi 中可以使用 :k 來查看它所屬的類型。

[2]: 你可以從它所屬的模塊名 Data.Functor.Foldable 中看到這樣的暗示。這個類原本就叫 Foldable，由於與標準庫中的 Foldable 重名，才改為 Recursive。

推薦閱讀：

相關文章