コンビネータ一覧表

この間Gaucheで作ったラムダ式からの変換プログラム(とその後の調査)からわかったことを表にまとめてみた。

name	in	out	memo
I	x	x	S K _ , W K , C K _ , R _ K
M	x	x x	O I , W I , W T
Y	x	x (Y x)	M2 L , U U , M2 (B M2 B)
i	x	x S K	V S K , S (O (K S)) (K K)
K	x y	x	K
KI	x y	y	K I , S K
T	x y	y x	C I , S (K O) K
W	x y	x y y	S1 I , S S (K I) , S T , C W1
W1	x y	y x x	C W , W V , M2 R , H R
W2	x y	x y x	W C , S S K
L	x y	x (y y)	Q M , W* B , R M B
O	x y	y (x y)	S I , Q Q W
U	x y	y (x x y)	B O M , L O
M2	x y	x y (x y)	W S , B M , S S I
C	x y z	x z y	S (D S) (K K) , C R , R R R
R	x y z	y z x	D T , C C , J T
V	x y z	z x y	C* T , C F
F	x y z	z y x	C V , C* R
B	x y z	x (y z)	S (K S) K , C Q , C* Q1
Q	x y z	y (x z)	C B , R B R
Q1	x y z	x (z y)	C* B , C Q2 , J I
Q2	x y z	y (z x)	B Q T , C Q1 , R* B
Q3	x y z	z (x y)	B T , C Q4 , V* B , G I
Q4	x y z	z (y x)	C Q3 , F* B
S	x y z	x z (y z)	W** G
S1	x y z	y z (x z)	C S
H	w x y	w x y x	S R , W* C*
W*	w x y	w x y y	B W
C*	w x y z	w x z y	B C , C* R*
R*	w x y z	w y z x	C* C*
V*	w x y z	w z x y	C** C , C* F*
F*	w x y z	w z y x	C* V* , C** R*
D	w x y z	w x (y z)	B B
B1	w x y z	w (x y z)	D B
B3	w x y z	w (x (y z))	D1 B
G	w x y z	w z (x y)	D C
G2	w x y z	w z (w z) (x y)	G1 M2
J	w x y z	w x (w z y)	S (C* E) C
Φ	w x y z	w (x z) (y z)	B (B S) B
Ψ	w x y z	w (x y) (x z)	H* D2 , Γ (K K)
H*	v w x y	v w x y x	B H , W** C**
W**	v w x y	v w x y y	B W*
C**	v w x y z	v w x z y	B C* , C** R**
R**	v w x y z	v w y z x	B R* , C** C**
V**	v w x y z	v w z x y	B V* , C** F**
F**	v w x y z	v w z y x	B F* , C** V**
D1	v w x y z	v w x (y z)	B D
E	v w x y z	v w (x y z)	B B1 , D1 D
B2	v w x y z	v (w x y z)	D B1 , E B
D2	v w x y z	v (w x) (y z)	D D , D3 B
G1	v w x y z	v w z (x y)	B G
Γ	v w x y z	w (x y) (v w x y z)	Φ (Φ (Φ B)) B
D3	u v w x y z	u v w x (y z)	B D1
E^	t u v w x y z	t (u v w) (x y z)	E E

出力の並び順

	x y z	x (y z)	w x y z	v w x y z
x y z	I = C T	B = C Q	I	B I
y x z	T = C I	Q = C B	C	C* = B C
x z y	C = C R	Q1 = C Q2 = C* B = B C B	C* = B C	C** = B C* = C** R**
y z x	R = C C = B B T	Q2 = C Q1 = R* B = B Q T	R* = C* C*	R** = B R* = C** C**
z x y	V = C F = B C T	Q3 = C Q4 = V* B = B T	V* = C* F*	V** = B V* = C** F**
z y x	F = C V	Q4 = C Q3 = F* B = B Q3 T	F* = C* V*	F** = B F* = C** V**
x x y	M = W I = W T	W B	W	W* = B W
y y x	M1 = C M	M1* B = B O T	M1* = C* W	B M1*
x y y	W = C W1 = S T	L = Q M = W* B	W* = B W	W** = B W*
y x x	W1 = C W = W V	C L = Q3 M = W1* B	W1* = W* V*	W** V**
x y x	W2 = W C	C O = H B	H = W* C*	H* = B H* = W** C**
y x y	W3 = W* T	O = W3* B	W3* = W** C	B W3*

W2,W3,D3は勝手に名前をつけただけ。正式な名前は不明。
本当はW2のところがHになるべきだったんじゃないかという気がする。