SK-combinator

SK-combinator で遊んでみよう。

k x y = x
s x y z = x z (y z)

と、定義すると下のようなものが作れる。

(.) f g x = s (k s) k f g x = f(g x)
($) f x = id f x = f x
flip ($) x f = s (k (s id)) k = f x
flipA = s (k (s s)) (s (k k) k) a b c = b c a
flipB = s (s (k s) (s (k k) s) ) (k k) a b c = a c b
flipC = s (s (k s) (s (k k) (s (k s) (s (k (s id)) k)))) (k k) a b c = c a b

> s (k (s s)) (s (k k) k) 2 (^) 3
9
> s (s (k s) (s (k k) s) ) (k k) (^)  2 3
9
> s (s (k s) (s (k k) (s (k s) (s (k (s id)) k)))) (k k) 2 3 (^)
8

flip ($) は 二つ引数 x f をとり、f(x) を返す。
. は合成関数を作る。

う〜ん。順序対にあたるものを定義しよう。
F (J a b) = a
G (J a b) = b
となれば便利。真偽値を作ろう。

T = k
F = k id

H T (J a b) = a
H F (J a b) = b

となるような、(H,J)を用意したい。

J として、

flipC = (s (s (k s) (s (k k) (s (k s) (s (k (s id)) k)))) (k k))

H として、

flip ($) = s (k (s id)) k

をとろう。そうすると、条件を満たしている。

H T (J a b) = flip ($) T (flipC a b) = (flipC a b) T = T a b = k a b = a
H F (J a b) = flip ($) F (flipC a b) = (flipC a b) F = F a b = k id a b = a

ここで、Pair a b = (flipC a b) という抽象データ型を考えよう。(H T)を作用させると a が、(H F)を作用させると b が取り出せるので、これは順序対だと思ってよい。

自分で適当に考えてるから嘘だったら教えて。

蚊に刺されたので続き。

uncurry f (pair a b) = f a b
uncurry = s (s (k s) (s (.) (k (h k)))) (k (h (k id)))
= s (s (k s) (s (s (k s) k) (k (s (k (s id)) k k)))) (k (s (k (s id)) k (k id)))
curry f a b = f (pair a b)
curry = s (s (k s) (s (k k) (s (k s) k))) (k pair)
      = s (s (k s) (s (k k) (s (k s) k))) (k (s (s (k s) (s (k k) (s (k s) (s (k (s id)) k)))) (k k)))

uncurry な (+) :(\x -> (h k x) + (h (k id) x))