gì combinator này làm: s (sk)

Question

bây giờ tôi hiểu kiểu chữ ký của s (s k):

s (s k) :: ((t1 -> t2) -> t1) -> (t1 -> t2) -> t1 

Và tôi có thể tạo ra những ví dụ mà làm việc mà không có lỗi trong công cụ Haskell WinGHCi:

Ví dụ:

s (s k) (\g -> 2) (\x -> 3) 

trả về 2.

Ví dụ:

s (s k) (\g -> g 3) successor 

lợi nhuận 4.

nơi successor được định nghĩa như vậy:

successor = (\x -> x + 1) 

Tuy nhiên, tôi vẫn không có một cảm giác trực quan cho những gì s (s k) làm.

Bộ tổ hợp s (s k) có hai chức năng f và g. s (s k) làm gì với f và g? Bạn có cho tôi bức tranh lớn về những gì s (s k) không?

Answer 1

Được rồi, hãy xem ý nghĩa của số S (S K). Tôi sẽ sử dụng các định nghĩa sau:

S = \x y z -> x z (y z) 
K = \x y -> x 

S (S K) = (\x y z -> x z (y z)) ((\x y z -> x z (y z)) (\a b -> a)) -- rename bound variables in K 
     = (\x y z -> x z (y z)) (\y z -> (\a b -> a) z (y z)) -- apply S to K 
     = (\x y z -> x z (y z)) (\y z -> (\b -> z) (y z)) -- apply K to z 
     = (\x y z -> x z (y z)) (\y z -> z) -- apply (\_ -> z) to (y z) 
     = (\x y z -> x z (y z)) (\a b -> b) -- rename bound variables 
     = (\y z -> (\a b -> b) z (y z)) -- apply S to (\a b -> b) 
     = (\y z -> (\b -> b) (y z)) -- apply (\a b -> b) to z 
     = (\y z -> y z) -- apply id to (y z) 

Như bạn có thể thấy, nó chỉ là ($) với loại cụ thể hơn.