我正在尝试解决 codewars 上的 sure but can you SKI。它即将在 SKI 组合器中表达 lambda。来源在 https://repl.it/@delta4d/SKI

经过一些研究,尤其是 Combinatory Logic ,我能够解决除 xor 之外的所有情况。

我首先将 xor 翻译成

xor x y = if y
          then if x
               then false
               else true
          else x

这是
xor = \x y -> y (x false true) x
-- false = K I
-- true = K

将 lambda 应用于 SKI 规则,我得到了
\x.\y.y (x false true) x
\x.S (\y.y (x false true)) (K x)
\x.S (S I (K (x false true))) (K x)
S (\x.S (S I (K (x false true)))) K
S (S (K S) (\x.S I (K (x false true)))) K
S (S (K S) (S (K (S I)) (\x.K (x false true)))) K
S (S (K S) (S (K (S I)) (S (K K) (\x.x false true)))) K
S (S (K S) (S (K (S I)) (S (K K) (S (\x.x false) (K true))))) K
S (S (K S) (S (K (S I)) (S (K K) (S (S I (K false)) (K true))))) K

我已经检查了 http://ski.aditsu.net 上的 SKI 演示文稿,它工作正常。

Haskell 源代码编译,但运行时错误。

Codewars 报道:



我用 prettyPrintSKI $ Ap (Ap xor' false) true 对本地进行了测试,它报告:



无限类型是关于什么的?什么是刚性类型?

我在 oror = \x y -> x true y 上做同样的事情,它工作得很好。

  • https://www.codewars.com/kata/sure-but-can-you-ski-i
  • https://en.wikipedia.org/wiki/Combinatory_logic
  • http://ski.aditsu.net
  • 最佳答案

    问题来自 xλxy.y (x false true) x 的双重使用。它被迫同时拥有两种类型。由于 y 使用 xy 必须返回一些东西,比如 a 类型。现在这意味着 x false true 也是 a 类型。所以 a 类型的东西必须是 (b -> b -> a) (对于某些 b )。但这是不可能的,因为这意味着 a 必须包含自身。

    值得注意的是,您的解决方案是正确的。 SK,只是不是 Haskell 的类型系统。所以要修复我们不需要对不同类型使用两次 x 。那么为什么不用 λxy.y(x false true)(x true false) 使它们成为相同的类型呢?

    关于haskell - 在 SKI 组合器中表达 XOR,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50095962/

    10-11 18:34