滑雪变换,如何用功能语言编程
-
16-10-2019 - |
题
我面临以下序言代码。 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表达式中绑定变量的发生。
解决方案
您的Prolog代码几乎可以逐字化为ML或Haskell的模式匹配。当然,您需要为Lambda表达式定义自己的ADT。对于最佳的组合者和该集的转换,我建议参考 http://www.amazon.com/functional-programming-international-computer-science/dp/0201192497
其他提示
您可以直接使用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;它有效,但请检查是否在概念上是否正确)
不隶属于 StackOverflow