haskell - 这个组合器做了什么：s (sk)

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)有什么作用？你能给我大局观吗？fgs (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)

如您所见，它只是($)具有更具体的类型。