コンビネータ・プログラミングと汎コンビネータ／コンビネータ変換子

• コンストラクタ＝集合コンストラクタ： 圏の対象に集合を対応させる
• コンビネータ＝射コンビネータ： いくつかの圏の射から圏の射を作り出す

一般的には：

• コンストラクタ：|C|→|D|
• コンビネータ：|C|→Mor(D)

さらに一般的には：

• (n, m)-コンビネータ：|C|_n→|D|_m
• (0, k)-コンビネータ：|C|→|D|_k

(n, m)-コンビネータは、(n, m-1)-コンビネータの集合を対象とする圏になる。特に、(0, 1)-コンビネータ＝コンビネータは、(0, 0)-コンビネータ＝コンストラクタの集合を対象とする圏になる。

コンビネータを受け取ってコンビネータを返す関数を汎コンビネータまたはメタコンビネータ〈meta-combinator〉と呼ぶ。

基本コンビネータと基本汎コンビネータにより、ユーザー定義コンビネータを作る行為をコンビネータ・プログラミングと呼ぶ。コンビネータの域コンストラクタと余域コンストラクタの組をプロファイルと呼ぶ。

汎コンビネータ〈メタコンビネータ〉には次がある。

1. 縦結合 (;) = Seq
2. 直積 (×) = Prod
3. ペア <_, -> = Pair

基本コンビネータに、Dup があるので、

• Pair(c, d) = Prod(c, d)Dup

など、汎汎コンビネータは、

1. 縦結合 SEQ
2. 直積 PROD
3. ペア PAIR

これを使うと：

• Pair = SEQ(Dup, SEQ(Pair, Prod))

無限タワーになる。

それはともかく：

• プログラミング： 基本関数と基本コンビネータからユーザー定義関数を作る。
• コンビネータ・プログラミング： 基本コンビネータと基本汎コンビネータからユーザー定義コンビネータを作る。

汎コンビネータであって、コンビネータの圏から別のコンビネータの圏への関手になっているものをコンビネータ変換子と呼ぶ。コンビネータ変換子は、Φ, Ψ, Ξ などのギリシャ文字大文字で表す。

計算論の背景圏はコンビネータ付きの圏である。異なる背景圏は異なるコンビネータ・レパートリーを持っている。コンビネータ変換子で、背景圏のあいだを繋ぐ。