de Bruijn index の評価器 - まめめもunlambda から brainfuck への変換器を作ろうしていましたが、なぜか de Bruijn index のラムダ式の評価器を Haskell で作った時点で飽きました。そんな残骸ですが、メモ代わりに公開します。de Bruijn index でも代入の定義はやっぱり複雑なんですね。 de Bruijn index はラムダ式の記法の一種です。普通のラムダ式と違うのは、変数を文字列ではなく数字で表現するところです。その数字のある位置から左方向にλを数えていって、その数字番目のλで束縛された変数を指示します。例えば λx.x は λ 1 になり、λx.λy.x は λ λ 2 に、λf.λg.λx.f x (g x) は λ λ λ 3 1 (2 1) になります。詳しくは wikipedia:de Bruijn index を参照してください。 -- ラムダ式 (出力機能付き)
