ウィキペディアのラムダ計算の前任者関数の説明に行き詰まっています。
ウィキペディアには次のように書かれています。
PRED := λn.λf.λx. n (λg.λh. h (g f)) (λu.x) (λu.u)
誰かが削減プロセスを段階的に説明できますか?
ありがとう。
10472 次
5 に答える
30
わかりました。では、教会数字のアイデアは、関数を使用して「データ」をエンコードすることですよね? 機能する方法は、値を使用して実行する一般的な操作によって値を表すことです。したがって、他の方向にも進むことができ、物事がより明確になることがあります。
チャーチ数字は、自然数の単項表現です。Zでは、ゼロを意味Snし、 の後継者を表すためにを使用しましょうn。Z, SZ, SSZ, SSSZ... 同等の教会数字は 2 つの引数を取り、最初は に対応しS、2 番目は に対応し、Zそれらを使用して上記のパターンを構築します。したがって、引数fおよびが与えられた場合、x次のように数えることができます: x、f x、f (f x)、f (f (f x))...
PRED の機能を見てみましょう。
最初に、3 つの引数を取るラムダを作成しますn。これはもちろん、その前身が必要な教会の数字です。これは、fとxが結果の数字への引数であることを意味します。したがって、そのラムダの本体が一度にf適用されることを意味します。xよりも少ないn。
次に、 3 つの引数に適用さnれます。これはトリッキーな部分です。
Z前のものに対応する 2 番目の引数λu.xは -- 1 つの引数を無視して を返す定数関数ですx。
S前に対応する最初の引数は ですλgh.h (g f)。λg. (λh.h (g f))最も外側のラムダのみが適用されているという事実を反映するように、これを書き直すことができnます。この関数が行うことは、これまでの累積結果を取得し、g1 つの引数を受け取る新しい関数を返します。この関数は、その引数をapplyed to にg適用しfます。もちろん、これは絶対に不可解です。
それで... ここで何が起こっているのですか？と を直接置換することを検討してSくださいZ。ゼロ以外の数値Snでは、 はnにバインドされた引数に対応しgます。fしたがって、とxが外側のスコープにバインドされていることを思い出すと、次のように数えることができます: λu.x, λh. h ((λu.x) f), λh'. h' ((λh. h ((λu.x) f)) f)... 明らかな還元を実行すると、次のようになります: λu.x, λh. h x, λh'. h' (f x)...その時点でSはそれを適用しますが、 はそれZを無視します。したがって、最も外側のものを除いfて、それぞれに 1 つのアプリケーションを取得します。S
3 番目の引数は単純な恒等関数であり、最も外側の によって忠実に適用されS、最終的な結果を返します。適用される回数は、対応するレイヤーfの数よりも 1 回少なくなります。Sn
于 2012-01-10T01:32:00.120 に答える