オブジェクト指向におけるVisitorパターンは、F代数によるμ再帰を Church encoding したもの

某所で オブジェクト指向 (OOP) における Visitorパターン について話されていたので、自分の関数型プログラミングのメモ用に整理してみたいと思います。
（Twitterで書くには少し長すぎたので、こちらに整理）

2021/01/10 EDIT:
Church (Boehm–Berarducci) エンコーディングとVistorパターンについての具体的な事例は、こちらの記事が分かりやすいので、ご参照ください。

• Haskell for all: The visitor pattern is essentially the same thing as Church encoding

---

概要

OOP における Visitor パターンは、関数型プログラミング的に言えば、（パターンマッチする）F代数によるμ再帰を Church encoding したもの。

つまり、

F代数 = F a -> a 

について μ再帰を Church encoding した

μF = ∀a. (F a -> a) -> a

を関数適用して、結果 a を得ることに相当します。

---

解説

OOP でも関数型でも、再帰計算でやっていることとしては 「再帰的データ構造（構文）」 をいかに「解釈」して、計算結果を生み出すか？ ということに尽きます。

それぞれのプログラミングスタイルにおける「構文」「解釈」「結果」については、

• OOP (Visitor) における・・・

  • 構文 ＝ 構文のインターフェースと実装
    • e.g. interface Node, class Node1, class Node2
  • 解釈 ＝ 解釈のインターフェースと実装
    • e.g. Visitor<A> = (visit1: Node1 -> A, visit2: Node2 -> A)
  • 結果 ＝ accept → visit → accept → ... による相互再帰計算

• 関数型 (fold) における・・・

  • 構文 ＝ 関手の直和 e.g. data F x = Node1' | Node2' x x
  • 解釈 ＝ F代数 F a -> a
  • 結果 ＝ fold (μF と F代数) による再帰計算

ここで Visitor の型に注目すると、これは型の性質（普遍性）を使って
(Node1 + Node2) -> A と書けます。(+ はEither直和型)

なお、 Visitor パターンによる計算では class Node1、Node2 の 「再帰構造」のほか、計算結果を得るための「解釈」を含んでいます。
これを関数型で解釈すると、 Recursion Scheme と呼ばれるテクニックを使って、下記の3つの基本要素に分解することができます：

1. 再帰そのもの ＝ μ
2. 再帰を含まない 構文 ＝ 関手 F
3. 再帰を含まない 構文の解釈 ＝ F代数 F a -> a

Recursion Scheme によれば、 F に μ を適用したものを μF と書き、これが再帰的構文である Node1 + Node2 に等しくなります。つまり、

Visitor = μF -> A

と書け、 構文 μF に 解釈 Visitor を関数適用して、計算結果 A を得る ことができます。

これは冒頭の概要に書いた、 F代数 F a -> a と μF を使って a を得る 話と同じとみなすことができます。
実は、後者のこの計算のことを一般に Catamorphism （畳み込み） と呼び、次の計算を行います。

-- NOTE: fold, reduce とも呼ばれる
catamorphism : (F a -> a) -> μF -> a

これを一枚絵で表すと、こんな感じです。

• 参考： Recursion Schemes - haskell-shoen

ここで疑問になるのが、 F a -> a と μF は具体的にどのように作用するのか？ ということです。
ここで、 Church encoding の出番となります。

Church encoding の詳しい説明は今回割愛しますが、再帰的なデータ型である μF について、 内部にそのまま catamorphism の機能を持たせる という関数化（エンコーディング）を行うと、 μF を次のように書くことができます。

μF = ∀a. (F a -> a) -> a

すると、 F代数(解釈) F a -> a と 構文 μF = (F a -> a) -> a の作用については、単純な「関数適用」によって a を得る ことができるというわけです。

Visitor パターンでは、構文 μF が解釈 Visitor に関数適用される側 でしたが、Church encoding を使ったμ再帰では、関数にエンコードされた構文 μF が（F代数による解釈 F a -> a に対して） 関数適用する側 に回るのが、真逆になっていて面白いですね。

まとめ

OOPにおける Visitor パターンとは、「構文の解釈」のことであり、関数型では μ再帰とF代数 (μF, F a -> a) に分解して、Church encoding → 関数適用したものに等しい。

P.S.

P.S. Visitor パターンでは、構文としての Node が Visitor ＝解釈のインターフェースを知る必要がありますが、関数型ではその依存方向が不要。

P.S. この話に関連して、Expression Problem などの一長一短の話がよく出てきますが、関数型プログラミングに Open Union (Extensible variants) を導入すると回避可能と思われます。

P.S. 最近の再帰のお気持ち

https://twitter.com/inamiy/status/1345666800067829762