ラムダ式をS,K,Iへコンパイル

自由変数のないラムダ式を S, K, I のコンビネータで記述するためのプログラムを書いてみた．演習の課題で S,K,I 以外のコンビネータを S,K,I で書けという問題があるそうだけどそんなのはプログラムでやるものだし（Bなんか手でやる気がしない）．んで，毎度のごとく Haskell でコンパクトに．

data LExp = Lambda (Int, LExp)
          | Apply  (LExp, LExp)
          | Var    Int
          | S
          | K
          | I
ctc (Lambda (x, exp)) = let exp' = ctc exp in (ctc' exp' x)
  where
  ctc' (Apply (exp1, exp2)) x = Apply (Apply (S, ctc' exp1 x), ctc' exp2 x)
  ctc' (Var y) x = if y == x then I else Apply (K, Var y)
  ctc' l x = Apply (K, l)
ctc (Apply (exp1, exp2)) = Apply (ctc exp1, ctc exp2)
ctc x = x

ラムダ式 LExp はλ抽象，適用，変数と，コンビネータ S, K, I で．コンパイル自体はλ抽象を内側からコンビネータに変換していくだけ．変換はアプリケーションに関しては S にして，変数に関しては束縛されるなら I, そうでないなら K.

折角なのでコンビネータからラムダ式への変換（alpha変換, beta簡約）も書いて知ってるコンビネータも全部書いてみた CompileToCombinators.hs .