lambda - Erlang中的S组合器

Question

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

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

我在纸上理解 I=SKK 转换没有问题（就像这里介绍的：为了证明 SKK 和 II 是 beta 等价的，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 组合器。我试过：

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

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

我尝试像这样运行它：

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

任何帮助将不胜感激，因为我完全迷路了。

Answer 1

从 Erlang 外壳：

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.