Erlang中的S组合子

Question

我开始学习λ演算，需要在Erlang中实现I、S、K组合子。当然，S、K、I代表：

S = λxyz.xz(yz) K = λxy.x I = λx.x

我没有问题理解纸上的I=SKK变换（如此处所示：To prove SKK and II are beta equivalent, lambda calculus），但是似乎当涉及到函数式语言和高阶函数时，我就不理解了……

我已经成功实现了I和K（假设在模块test中）：

i(X) -> X.
k(X) -> fun(Y) -> X end.

此外，我知道如何运行 K x (K x) （SKK x = K x (K x)）。

kxk(X) -> (k(X))(k(X)).

但我无法写出S combinator。我尝试了：

s(X) -> fun (Y) -> fun(Z) -> X,Z (Y,Z) end end.

但是，我仍然无法将SKK x转换为x。

我尝试像这样运行它：

skkx(X) ->  s((k((k(X))))).

我需要帮助，因为我完全不知道该怎么做。

- Krodak

---

实际上，你的问题纯粹是符号表示上的。如果你理解了 beta-reduction 的工作原理，那么你一定理解这个想法。其余的只是符号表示。 - I GIVE CRAP ANSWERS

Answer 1

在Erlang shell中：

1> I = fun (X) -> X end.
#Fun<erl_eval.6.80247286>
2> K = fun (X) -> fun (Y) -> X end end.
#Fun<erl_eval.6.80247286>
3> S = fun (X) -> fun (Y) -> fun (Z) -> (X(Z))(Y(Z)) end end end.
#Fun<erl_eval.6.80247286>
4> ((S(K))(K))(42).
42

或者作为模块中的函数：

i(X) -> X.
k(X) -> fun(Y) -> X end.
s(X) -> fun (Y) -> fun (Z) -> (X(Z))(Y(Z)) end end.

- RichardC

---

好的，我仍然似乎有一些问题 :/ 在我的模块中，我有： i（X） - > X。 k（X） - > fun（Y） - > X end。 s（X） - > fun（Y） - > fun（Z） - >（X（Z））（Y（Z））end end。 skk（X） - >（（s（k））（k））（X）。当我运行（tppr是模块名称）： tppr：skk（x）。 我收到： **异常错误：坏函数k 在函数tppr：'-s/1-fun-0-'/3中我错过了什么？ - Krodak

在你定义 skk(X) ->((s(k))(k))(X) 中，你写的是小写字母 k - 这是原子 'k'，而不是函数 k/1。如果你改为写 skk(X) ->((s(fun k/1))(fun k/1))(X)，它应该可以工作。 - RichardC

谢谢，是的，就是那样，相当愚蠢，我必须承认 ;) - Krodak