滑雪变换，如何用功能语言编程

Question

我面临以下序言代码。 y表达式[x] >>代表lambda表达式lambda xy代码消除了lambda，并在s，k和i上给出了组合表达式：

convert([X]>>Y,'I') :- X==Y, !.
convert([X]>>Y,apply('K',Y)) :- var(Y), !.
convert([X]>>([Y]>>Z),R) :-
     convert([Y]>>Z,H), convert([X]>>H,R).
convert([X]>>apply(Y,Z),apply(apply('S',S),T)) :-
     convert([X]>>Y,S), convert([X]>>Z,T).
convert([_]>>Y,apply('K',Y)).

这是它的工作方式：

 ?- convert([X]>>([Y]>>apply(Y,X)),R).
 R = apply(apply('S', apply(apply('S', apply('K', 'S')), 
  apply('K', 'I'))), apply(apply('S', apply('K', 'K')), 'I'))

假设我想编码相同 转换 在Haskell，ML等。我怎样才能做到这一点？我可以直接使用功能编程语言中可用的lambda表达式吗？还是我必须回归到一些元编程设施？

此致

PS：上面的代码不是导致非常短的滑雪表达式的滑雪转换。更好的代码可以检查lambda表达式中绑定变量的发生。

Answer 1

您的Prolog代码几乎可以逐字化为ML或Haskell的模式匹配。当然，您需要为Lambda表达式定义自己的ADT。对于最佳的组合者和该集的转换，我建议参考 http://www.amazon.com/functional-programming-international-computer-science/dp/0201192497

Answer 2

您可以直接使用lamdba表达式。在哈斯克尔：

i x = x
k x = \y -> x
s x y z = x z $ y z

r = s (s (k s) (k i)) (s (k k) i)

-- r 3 (+5) -> 8

（请注意，我不知道滑雪，此片段是Wikipedia上的定义转换为Haskell；它有效，但请检查是否在概念上是否正确）