Recursion Schemes（一）新手入門

來自專欄貓爪56 人贊了文章

序章

時間回到1991年，Erik Meijer， Maarten Fokkinga， 和 Ross Paterson 發表了一篇論文，Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire 這篇論文在即使在今天看來仍是函數式編程領域的經典之作。儘管在函數式編程社區之外，這篇論文並不廣為人知，但它的貢獻仍然是巨大的：作者使用範疇論表達了一組被稱為 Recursion Schemes 的簡潔組合子。使用這組組合子，可以自動化地完成嵌套式數據結構的遞歸遍歷。儘管 Recursion Schemes 的提出早於 Erik Meijer 等人的工作，這篇文章將範疇論中的強大抽象能力應用於遍曆數據結構這一主題——這正是範疇論如何使我們日常編程任務變得簡潔而富有秩序的一個有力例證。

嵌套式數據結構幾乎出現在每一個編程領域中，從3D繪圖到文件系統，遍歷這樣的數據結構是非常常見的，常見到程序員們幾乎感知不到他們做了這件事。因此，泛化遞歸和遍歷這一動作幾乎立即就可以為真實世界帶來好處：使用新的泛化的遍歷模式取代掉那些舊的依賴於類型的遍歷函數。而且通過將如何遍曆數據和如何使用數據解耦，可以減輕程序員們的對代碼的理解負擔，而更專註於如何使用數據這一核心行為。無論怎樣的數據結構，鏈表，目錄樹，控制流圖還是資料庫表項，使用 Recursion Schemes 都可以準確有序地遍歷它們。而且 Recursion Schemes 並不依賴與編程語言或編程環境——任何將函數作為一等公民的語言都可以使用 Recursion Schemes，例如 Clojure 的 clojure.walk API 就廣泛使用了 Recursion Schemes 來遍歷 s-expression 和 map。

實際上 Meijer 等人的工作非常成功，以至於基本上可以說函數式編程缺少 Recursion Schemes 就等於在命令式編程中使用 goto。僅管這裡引用 Djikstra 寫給 ACM 的那封廣為人知的信不免有些陳詞濫調，但是這個比喻是恰當的：只使用 for 和 while 而不使用 goto 使得命令式語言的控制流和諧簡潔，對於函數式語言，使用 Recursion Schemes 而非為對數據結構手寫遞歸計算，帶來了相似的效果。這一見解非常深刻，以至於我要再重複一遍：Recursion Schemes 之於函數式編程範式，就如同 for 和 while 之於命令式編程範式。

儘管 Bananas, Lenses, Envelopes and Barbed Wire 論文發表時間遠早於 Haskell 語言的誕生時間，本文仍選擇使用 Haskell 作為編程語言來展示文中背後的想法[1]。如果你並不十分熟悉 Haskell， 別慌： 理解本文的思想不需要您成為一個 Haskell 專家。我實際上只用到了 Haskell 的語法以及 algebraic data types。我會使用一些語法特性來更好地展示 Recursion Schemes 背後的思想，在我使用這些語法特性的時候，我都會解釋一下它們的作用。如果您之前完全沒有 Haskell 的使用經驗，或許閱讀 Learn You a Haskell 的前幾章的內容有助於您理解本文。

本文的例子會從一個簡單的類型完備的語法樹的定義開始，接著我會展示在這樣一顆語法樹上進行泛化遍歷和修改樹結構是相當困難的。接著我們會使用 Haskell 的語法特性以及強大的 parameterized data types 來重新定義語法樹，而就在我們使用常見的 Haskell 語法一步步定義和描述遞歸模式的過程中，Recursion Schemes 自然而然地就會被導出。

如果你對本文中使用的代碼感興趣，你可以在這個 Github 倉庫 中找到對應的代碼。代碼中還包括一組單元測試以用來驗證代碼的正確性。

遞歸的語法樹

我們首先來看一下在 Haskell 中使用 algebraic datatype 來最簡單地表達一個語法樹應該怎樣做。

data Lit = StrLit String | IntLit Int | Ident String deriving (Show, Eq)data Expr = Index Expr Expr | Call Expr [Expr] | Unary String Expr | Binary Expr String Expr | Paren Expr | Literal Lit deriving (Show, Eq)data Stmt = Break | Continue | Empty | IfElse Expr [Stmt] [Stmt] | Return (Maybe Expr) | While Expr [Stmt] | Expression Expr deriving (Show, Eq)

可以看到這已經是一個相當不錯的語法樹了：它簡單直白，可以直接應用在一些語法樹解析庫上，例如 attoparsec 或 Peggy。然而為這樣的一棵語法樹寫一個操作子節點和子表達式的函數是一件非常乏味的工作。下面是一個例子，flatten 函數接受一棵語法樹，並遞歸地刪除其所有的代表括弧的 Paren 節點：

-- this would turn the expression -- (((anArray[(10)])))-- into-- anArray[10]flatten :: Expr -> Expr -- base case: do nothing to literalsflatten (Literal i) = Literal i-- this is the important case: we shed the Paren constructor and just -- apply `flatten` to its contentsflatten (Paren e) = flatten e-- all the other cases preserve their constructors and just apply -- the flatten function to their children that are of type `Expr`.flatten (Index e i) = Index (flatten e) (flatten i) flatten (Call e args) = Call (flatten e) (map flatten args) flatten (Unary op arg) = Unary op (flatten arg) flatten (Binary l op r) = Binary (flatten l) op (flatten r)

可以看到這段代碼難以忍受地醜陋，並且難以維護。6行代碼中的4行代碼實際上在完成一件非常無聊但又不得不做的工作，確保 flatten 函數在可以正確地在子表達式下遞歸下去。這樣的代碼不僅書寫十分無趣，而且之後對Expr的任何改變（例如增加了新的域或語法關鍵字）都必須修改這個函數。（我把這種遞歸行為稱為顯式遞歸，以與 Recursion Schemes 提供的隱式遞歸進行區別）而且，這樣的定義方式極易出錯——顯式遞歸引入的語法噪音使得檢查是否有子表達式遺漏變得非常困難。而這樣的疏漏就有可能引入災難性的 bug。

我們可以使用 apply 函數為這段混亂的代碼帶來些許秩序，它接受一個以 Expr 為參數的函數 f 並應用這個函數操作 Expr 和它所有的子表達式：

applyExpr :: (Expr -> Expr) -> Expr -> Expr -- base case: applyExpr is the identity function on constantsapplyExpr f (Literal i) = Literal i-- recursive cases: apply f to each subexpressionapplyExpr f (Paren p) = Paren (f p) applyExpr f (Index e i) = Index (f e) (f i) applyExpr f (Call e args) = Call (f e) (map f args) applyExpr f (Unary op arg) = Unary op (f arg) applyExpr f (Binary l op r) = Binary (f l) op (f r)

通過隔離遞歸這一操作，我們可以將 flatten 函數從6行減為2行，在 flatten 函數內部，我們只需要關注 Paren 節點即可，而將其他節點上的遞歸操作交給 applyExpr 函數即可：

flatten (Paren e) = flatten e flatten x = applyExpr flatten x

這使得我們可以非常方便地書寫和維護一段代碼了。apply 函數將負責所有平凡情況的處理，並且完成在子表達式上的遞歸，而我們寫的函數只需要負責那些我們感興趣的部分即可，例如，處理 Paren 節點，酷！

但我們暫且不要高興得太早，實際上我們並沒有杜絕模板文件，這裡仍有出現 bug 的可能：applyExpr 僅僅只是隔離了模板與內容，每當我們定義了新的語法或類型，我們都需要重寫 applyExpr 函數。但實際上一個異常聰明的編譯器，例如 GHC，可以幫助我們完成這件事。不過首先我們需要對 Expr 數據類型進行適當的修改，以使其具有更加泛化的表達能力。

參數化類型

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

Expr 的新定義與我們之前的完全相同，除了我們加入了一個類型變數 a 並且用它將所有遞歸出現的 Expr 替換掉。換句話來說，我們對 Expr 的子表達式完成了參數化。因此我們也需要修改 applyExpr：我們向下層的函數類型不再是 Expr -> Expr 而變為了 a -> a：實際上我們甚至可以定義為 a -> b，這樣輸入函數就具備了改變底層 Expr 的底層子表達式的能力。

apply :: (a -> b) -> Expr a -> Expr b

敏銳的讀者已經察覺到了這個函數與內置與 list 的 map 函數多麼相似：

-- `map` takes a function (a -> b) and makes it operate on lists containing as map :: (a -> b) -> [a] -> [b]

這並不是一個巧合，實際上 apply 函數就是和 map 同構的——你可以將這兩個函數都看作將函數 f 提升並應用於更大的數據類型上，這個更大的數據類型可以是 Expr 也可以是列表([])。而這種映射的模式實際上在 Haskell 中十分常見，以至於它的泛化版本正是 Haskell 中的一個核心概念：類型類 Functor 代表了所有的能提供類似映射功能的函數，稱作 fmap[2]:

class Functor f where fmap :: Functor f => (a -> b) -> f a -> f b

無數的類型——列表，樹，可選值（Maybe），IO 操作，甚至於函數本身，都實現了 Functor 類型類。實際上由於這個函數如此常見，而實現 fmap 又非常直白，GHC 提供了一個內置的機制來幫你實現 fmap：我們只需要將 Functor 加入 Expr 的推導聲明中，就跟 Show 和 Eq 一樣：

{-# LANGUAGE DeriveFunctor #-}data Expr a = Index a a | Call [a] | Unary String a | Binary a String a | Paren a | Literal Lit deriving (Show, Eq, Functor) -- fmap for free

甚至於說，你可以導出 Foldable 和 Traversable 這些類型類，這為我們訪問和遍歷 Expr 提供了豐富的手段，在我們為 Functor Foldable 和 Traversable 所提供的豐富功能震驚時，也必須要注意到，現在的參數化版本 Expr 其實和我們之前的版本並不完全一樣！

我們之前版本的 Expr 因為在子節點上是遞歸的，所以我們可以表達任意嵌套的 Expr，但我們的新版本定義做不到這一點。一個任意嵌套的 Expr，我們在葉子節點使用 Lit :

• Expr Lit 表示一個沒有子表達式的表達式
• Expr (Expr Lit) 表示一個含有一層子表達式的表達式
• Expr (Expr (Expr Lit)) 表示一個含有兩層的，以此類推

為了使我們的參數化版本定義的 Expr 具備這種特性，我們需要一種類型，這種類型可以在當我們確定 Expr a 中的 a 類型時，得到一個嵌套任意多層 Expr 子表達式的類型。

type NestedExpr = Expr (Expr (Expr (Expr …)))

為了得到這種類型，我們需要一些技巧，使我們可以用有限長的語句，構造任意多層嵌套類型的 Expr。

不動點

考慮一個 Y-組合子，給定一個輸入為一個參數的函數 f，y(f) 實際上就表示了不斷將 f 應用在自己本身上：

y(f) = f(f(f(f(f ...))))

敏銳的讀者們想必已經察覺 y(f) 的形式與我們所需要的 NestedExpr 的形式非常相似，如果我們把一個 Y-組合子整合進類型系統的話，我們就可以描述 Expr 不斷應用於自己這樣的形式了，而整合的過程只需保持與在值域上作用於函數的 Y-組合子的同構即可。這樣我們就可以描述任意嵌套的表達式 Expr a 了，其中 a 代表任意嵌套的表達式 Expr。

type Y t = t (t (t (t (t ...))))

實際上這就是不動點[3]的定義：我們稱 y(f) 是函數 f 的一個不動點，而 Y Expr 就是函子 Expr 的一個不動點。而關鍵性的一點在於，我們可以在類型系統中構建 Y-組合子，這樣就可以表示 Expr 和其子表達式間相似這一本質特徵。

我們需要一個類型 Y，它接受另一個類型 f，它將 f 應用到類型為 (Y f) 的子節點上，我們定義這樣的 Y 類型為 Term，而它的構造函數為 In，表示我們將一層的遞歸變成了固定形式，接著我們定義 out 函數來輔助解析 Term。

data Term f = In (f (Term f))out :: Term f -> f (Term f) out (In t) = t

接著我們非常自然地應用 Expr 到 Term 上：

Term Expr = In (Expr (Term Expr))out :: Term Expr -> Expr (Term Expr)

從這個定義我們可以看到，給定一個 Term Expr，我們可以使用 out 函數將其轉化為一個 Expr 表達式，而它的子表達式是 Term Expr。這表示我們對一個 Term Expr 連續應用 out 函數就可以把它解析成任意嵌套的 Expr：Term Expr 可以變成 Expr (Term Expr) 接著變為 Expr (Expr (Term Expr))，以此類推。這種使用函子不動點來定義遞歸類型的風格，正是一個 codata 的例子，完整地討論 codata 理論（還有 codata 的各種變種）已經超出了本文的範圍。感興趣的話，這裡有一個非常詳盡的介紹。

泛化遍歷

在本章，我們將為使用不動點和函子來定義我們的數據結構打下基礎。

考慮一個自底向上的遍歷過程，我們用偽碼來看看一個函子的不動點遍歷需要具備哪些功能：

我們使用 ? 自底向上地遍歷一個 Term 1. 解析 Term 以訪問它的所有孩子 2. 使用 ? 遞歸地應用於 Term 的每一個孩子 3. 重新封裝好 Term 4. 應用 ? 到 Term 上

我們定義函數 bottomUp 來總結剛才偽碼所做的過程。

bottomUp :: Functor a => (Term a -> Term a) -> Term a -> Term a

給定一個從 Term 到 Term 的函數 fn，我們先用 out 函數對 Term 解包，接著使用 fmap (bottomUp fn) 來遞歸遍歷它的每一個子節點，接著使用 In 重新封裝，最後只需要應用 fn 得到最後結果即可。其中 fmap bottomUp 的調用完成了函數中最重要的類型提升部分：它使用函子完成了對所有子節點的遞歸遍歷。

我不會分別定義 fn 的參數和 Term 的參數，取而代之的是我準備直接定義 bottomUp 函數，直接把 out，fmap bottomUp，In 和 fn 組合起來。這裡會用到在 Control.Arrow 中的 >>> 操作符，從左向右結合，f >>> g x 等價於 g(f(x))。這個風格稍顯古怪，實際上自右向左的結合 . 更加常見，這裡我們使用這個風格是因為這樣我們將對於函數間的調用順序有一個清晰的可視化，而這一順序之後會變得十分重要。

現在我們按自左向右的順序使用 >>> 操作符將函數拼接起來：

bottomUp fn = out -- 1) unpack >>> fmap (bottomUp fn) -- 2) recurse >>> In -- 3) repack >>> fn -- 4) apply

於是，我們的第一個 Recursion Schemes 函數出現了！我們可以使用 bottomUp 函數完成了一個類型安全並且支持泛型的組合子，使其可以遞歸地對任何函子進行變換：比如我們的 Expr，或者列表，多叉樹，或任何其他結構。老實說，這非常酷！我們再一次重寫之前的 flatten 函數，以使它支持嵌套了任意多層 Expr 的 Term:

flattenTerm :: Term Expr -> Term Expr flattenTerm (In (Paren e)) = e -- remove all Parens flattenTerm other = other -- do nothing otherwiseflatten :: Term Expr -> Term Expr flatten = bottomUp flattenTerm

我們的上一個使用 apply 的 flatten 版本不可謂不簡潔，但是新的版本更加優雅：我們的 bottomUp 函數使用 Recusion Scheme 使我們徹底規避了定義遞歸形式。我們可以專註於 flatten 函數的行為本身——從語法樹中去除所有的括弧節點——而完成這一函數也僅僅只需 2 行。而且使用 bottomUp 和 flattenTerm 比顯式的定義整個遞歸函數更加簡明清晰。相比於我們之前版本的 flatten，我們已經獲得了不小的進展，我想不到比這更簡潔的表達方式編碼方式了。

但是我們還是不要就此止步為好，讓我們考慮一下自底向上遍歷的天然對偶形式，自頂向下遍歷一個 Term：

我們使用 ? 自頂向下地遍歷一個 Term 1. 應用 ? 到 Term 2. 解析 Term 以訪問它的所有孩子 3. 使用 ? 遞歸地應用於 Term 的每一個孩子 4. 重新封裝好 Term

注意到這些指令與自底向上遍歷的指令驚人地相似，只需要我們逆序整個流程，並把解析和封裝交換下位置，二者就完全相同了，而美妙的是：我們的代碼也可以這樣做。代碼中我們只需要將自左向右的操作符 >>> 替換為自右向左的操作符 <<<[4]，並把 In 和 Out 交換位置就可以了！

topDown, bottomUp :: Functor f => (Term f -> Term f) -> Term f -> Term ftopDown f = In <<< fmap (topDown f) <<< out <<< f bottomUp f = out >>> fmap (bottomUp f) >>> In >>> f

我們通過「反轉箭頭」就完成了自頂向下自底向上這一組對偶概念的表達，同時保持類型安全並不失一般性，而且這些概又可由 Haskell 的兩大核心概念函子和不動點自然導出，還有什麼比這更激動人心呢？

結語

自頂向下和自底向上是 Recursion Schemes 中最為簡單的一組。我們只是接觸到了 Bananas, Lenses, Envelopes and Barbed Wire 論文的一些初級應用。在下一篇介紹中，我會談談 Recursion Schemes 的另外兩個變種以及如何讓 Recursion Schemes 更加泛化。

我要感謝所有閱讀這篇文章的人，特別是 Nate Soares 和 Manuel Chakravarty，我還要感謝 Colin Barrett，與我熬夜討論文章的細節，如果你有任何關於本文的評論或疑問，可以在 Twitter 上找到我。

下一章我們將定義並討論 catamorphisms 和 anamorphisms。

譯者後記

譯者也是還在 Haskell 學習中，本來是在讀 Pearls Functional Algorithm Design，一不留神就掉進了 Recursion Schemes 的坑裡，目前來看坑也是有越開越大的趨勢。本文翻譯自 Adventures in Uncertainty 博客，關於一些術語和技術的翻譯可能不夠準確，原文的神韻也多有折扣，懇請大家指正。閱讀的過程中如果遇到什麼問題，也歡迎與我交流討論。

最後再次感謝大家的閱讀！

[1]:實際上在 Bananas, Lenses, Envelopes and Barbed Wire 一文中，Meijer 等人並沒有使用任何一種特定的編程語言，而是使用了一套由 Bird-Meertens formalism 導出的符號。（Bird-Meertens formalism 是一套基於 Recursion Schemes 的程序構造演算系統，Meijer 的博士論文就是在討論一套使用 Bird-Meertens formalis 的編譯器規範）這套演算系統也被稱為 「Squiggol」，這是源於它扭曲的符號記法。儘管記法本身十分詳盡，單其中的一些描述符號如「香蕉括弧」（形如(||)）和 「凹透鏡」（形如[()]）仍令人倍感困惑。

[2]:你或許會好奇既然 map 只是 fmap 的一個特化，那麼為什麼 Haskell 提供了 map 和 fmap 兩個函數，而這正是 Haskell 社區的一個核心論點。正如 Typeclassopedia 的作者 Brent Yorgey 所說：「對於一個 Haskell 的初學者，當錯誤的使用 map 函數時，他顯然更想看到一個關於列表的錯誤，而非一個關於函子的錯誤」。

[3]:完整地討論不動點的優雅與重要顯然超出了本文的範圍，對此感興趣的讀者可以閱讀 Raymond Smullyan 的一篇精彩教材 Mock a Mockingbird 或是閱讀 Reginald Braithwaite 的 combinators.info。

[4]:即為 Haskell 中的 . 操作符。