FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

11.08
Thu
わすれそうなのでちょっとしたTips

LispとかHaskellすこーし触ったところなんでもラムダ計算ってのが大事らしいので

ラムダ計算勉強中です

で、ラムダ式で自然数を表すのは

関数を何回適用したかで表すっぽいのですが、(チャーチ数)

こんな感じ


0 := (\f.(\x.x))
1 := (\f.(\x.(f x)))
2 := (\f.(\x.(f (f x))))
.
.
.


\fxみたのを\f.\xで表したのをカリー化されてると呼んでいいんですよね...?たぶん

ここで自然数nを受け取った時にn+1を返すsuccを作りたいのですが

ウィキペディアを見るとsuccは

\nfx.f(n f x)


と書いてあります

他のラムダ計算を解説してくださってるブログにもそう書いてあったんですが、

まったくの初心者の僕にはいまいちわからなかったので、いろいろやってみる

あとラムダ計算は左結合だってことを忘れてた!!ようするに左から適用とかしてく!!

自分なりにわかりやすくなるように変形してみた

(\n.(\f.(\x.(f (n (f x) )))))

だけど上の変形はまちがってた

こうゆうふうに変形するなら

こうですね

(\n.(\f.(\x.(f ((n f) x)))))


なぜならラムダ式は左結合だからnにfを先に適用しなきゃいけないから

ということでこれに0(\f.(\x.x))を適用させると、

(\n.(\f.(\x.(f ((n f) x))))) (\f.(\x.x))
-> (\f.(\x.(f (((\f.(\x.x)) f) x))))
-> (\f.(\x.(f ((\x.x) x))))
-> (\f.(\x.(f x)))


ということで、1になりました。

これでnを渡すとn+1が返ってくるはずです
スポンサーサイト

comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/147-f8af711a
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。