KコンビネータとSコンビネータ
OCaml勉強中。KコンビネータとSコンビネータが出てきた。
OCamlでfun式と関数適用の組み合わせ「のみ」で表現できる関数はSとKのを関数適用で組み合わせることですべて表現できることが知られています。
# let s x y z = x z (y z);; val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun> # let k x y = x;; val k : 'a -> 'b -> 'a = <fun>
で、s k k が恒等関数になると。
# s k k;; s k k;; - : '_a -> '_a = <fun>
以下、いろいろ試してみた。
# k (s k k);; - : '_a -> '_b -> '_b = <fun> # k (k (s k k));; - : '_a -> '_b -> '_c -> '_c = <fun> # k (k (k (s k k)));; - : '_a -> '_b -> '_c -> '_d -> '_d = <fun> # k (k (k (k (s k k))));; - : '_a -> '_b -> '_c -> '_d -> '_e -> '_e = <fun>
fun x y z -> xをやろうとしたけど、出来なかった。どうするんだろう。