这个组合器是做什么的:s（s k）

Question

我现在明白的类型签名 s (s k):

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

我可以在Haskell WinGHCi工具中创建工作没有错误的示例:

例子：:

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

申报表 2.

例子：:

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

申报表 4.

哪里 successor 被定义为如此:

successor = (\x -> x + 1)

尽管如此，我仍然没有 直观的感觉 为了什么 s (s k) 确实如此。

组合器 s (s k) 接受任意两个函数 f 和 g.做什么？ s (s k) 做与 f 和 g?你能给我吗？ 大图景 关于什么 s (s k) 求你了吗？

Answer 1

好吧，让我们看看什么 S (S K) 手段。我将使用这些定义:

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)

正如你所看到的，这只是 ($) 具有更具体的类型。