コンビネータの例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/10 14:50 UTC 版)
「コンビネータ論理」の記事における「コンビネータの例」の解説
もっとも単純なコンビネータの例は、以下のように定義される恒等コンビネータIである。 (I x) = x もうひとつの単純なコンビネータはKで、定数関数を作る。(K x)はどんな引数に対してもxを返す関数である。そして、Kはこのように定義する: ((K x) y) = x もしくは、伝統的な複数の適用の表記に従えば (K x y) = x 三つ目のコンビネータは、適用を一般化したSである。 (S x y z) = (x z (y z)) Sは、それぞれにzを適用したあとxをyに適用する。別の言い方をすれば、zという環境においてxをyに適用する。SとKがあれば、Iは不必要である。なぜなら、他の二つでこのようにして表現できるからである。 ((S K K) x)= (S K K x) = (K x (K x)) = x すべての項xに対して((S K K) x) = (I x)が成り立つが、(S K K)自身はIとは同じではない。これらの項は外延的に同値である。外延的同値は関数の同値という数学的な概念である。二つの関数が、同じ引数に対して常に同じ結果を返すならばそれは等しい。対照的に、原始的なコンビネータと一緒にあるそれらの項自身は、内包的同値という概念を捉える。十分な引数が与えられたときに、原始的なコンビネータに展開されるまで同じ形をもつ時だけ、それらは同値である。 恒等関数を実装するにはたくさんの方法がある。(S K K)とIはそれに含まれている。さらに、(S K S)もそうである。今後、同値という言葉を外延的同値を示し、等しいを同じコンビネータを示すのに使う。 さらに面白いコンビネータは、再帰を実装するために使える不動点コンビネータ(Yコンビネータ)である。
※この「コンビネータの例」の解説は、「コンビネータ論理」の解説の一部です。
「コンビネータの例」を含む「コンビネータ論理」の記事については、「コンビネータ論理」の概要を参照ください。
- コンビネータの例のページへのリンク
