研究(2)コンビネータを学ぶのに便利な一つの方法

コンビネータに型がつけられることは研究(1)で述べました。
これを利用することで、1ステップずつ確かめながら
コンビネータの変換を試すことができます。
以下のコードは等価な変換をしながらsコンビネータをb,c,wであらわしたものです。
コードはhaskellです。
まず最初にsコンビネータの定義をtestで定義します。
その後コンパイルしてghciで:t testとやることでtest :: (t1 -> t2 -> t3) -> (t1 -> t2) -> t1 -> t3という型情報が得られます。
次に等価な変換を行うので型情報は変わらないので、test2を同じ型で定義してから
test2の実装を書いていきます。
test3以降も同様です。
もちろんこれは一つのやり方ではありますが、先にtest2を書いてからghciで型情報をtestとtest2とで比べてみるという方法でも良いです。
もしtest2の等価変換が間違っていたら型エラーとなってコンパイルできません。
test2では、dコンビネータ(b b)を使って括弧を外しています。
test3では、c*コンビネータ(プログラムではcs)を使って引数の順序を入れ替えています。
test4では、w***コンビネータ(プログラムではwsss)を使って二つのzを一つにまとめています。
test5で完成で、test4をイータ変換しています。

csやwsはonce removed,cssやwssはtwice removedなコンビネータです。
cssとcss’,wsssとwsss’は同じものです。
これらを作成するときにも上で述べた手法がもちろん使えます。

b x y z = x (y z)
c x y z = x z y
cs = b c
css = b cs
css' x y z w u = x y z u w
w x y = x y y
ws = b w
wss = b ws
wsss = b wss
wsss' x y z w u = x y z w u u
-- S combinator
test :: (t1 -> t2 -> t3) -> (t1 -> t2) -> t1 -> t3
test x y z = x z ( y z)
test2 :: (t1 -> t2 -> t3) -> (t1 -> t2) -> t1 -> t3
test2 x y z = (b b) x z y z
test3 :: (t1 -> t2 -> t3) -> (t1 -> t2) -> t1 -> t3
test3 x y z = cs (b b) x y z z
test4 :: (t1 -> t2 -> t3) -> (t1 -> t2) -> t1 -> t3
test4 x y z = wsss cs (b b) x y z
test5 :: (t1 -> t2 -> t3) -> (t1 -> t2) -> t1 -> t3
test5 = wsss cs (b b)