functional-programming - SKI 变换，如何用函数式语言编程

Question

我面临以下序言代码。表达式 [X]>>Y 成立对于 lambda 表达式 lambda X.Y.该代码消除了 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 表达式吗直接在函数式编程语言中？或者我必须回归到某些元编程工具？

最好的问候

P.S.: 上面的代码不是导致很短的SKI转换滑雪表达。可以使用更好的代码来检查是否出现lambda 表达式主体中的绑定(bind)变量。

Answer 1

您的序言代码几乎可以逐字翻译成 ML 或 Haskell 的模式匹配。当然，您需要为 lambda 表达式定义自己的 ADT。对于最佳的一组组合器和该组的转换，我建议引用 http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497