用 Ocaml 编写 Z 组合器

Question

我是 lambda 演算的新手，我发现语法有时对我来说不明确。\n具体来说，我想知道如何理解 Z 组合器：

\n

Z = \xce\xbb f. (\xce\xbb x. f (\xce\xbb v. xxv)) (\xce\xbb x. f (\xce\xbb v. xxv))\n

如何在 OCaml 中编写它？\n更新：\n这样写时出现错误：

\n

 fun f-> let g = fun x -> f(fun v-> x x v)in g g;;\n

错误：此表达式的类型为 'a -> 'b -> 'c\n但预期的表达式为 'a\n类型变量 'a 出现在 'a -> 'b -> 'c 内

\n

Answer 1

输入 Z 组合器需要允许递归类型（使用选项-rectypes）或将类型递归装箱在类型构造函数内：

type 'a fix = Fix of ('a fix -> 'a)
let z f = 
  (fun (Fix x as fx) -> f (fun v -> x fx v)) 
  (Fix (fun (Fix x as fx) -> f (fun v -> x fx v)))

本质上，我们正在替换

x x v

这需要x接受自身作为参数，从而导致递归'a -> 'b -> 'c as 'a类型

x fx v

将递归类型包装为('a -> 'b) fix -> 'a -> 'b