在 Ocaml 中编写 Z 组合子

Question

我是 lambda 演算的新手，我发现语法有时对我来说有歧义。具体来说，我想知道如何理解 Z 组合子：

Z = λ f. (λ x. f (λ v. xxv)) (λ x. f (λ v. xxv))

OCaml中怎么写？更新：像这样写时出现错误：

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

错误：此表达式的类型为 'a -> 'b -> 'c 但表达式应为 'a 类型类型变量 'a 出现在 'a -> 'b -> 'c

中

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 by

x fx v

其中框递归类型为('a -> 'b) fix -> 'a -> 'b

Writing the Z combinator in Ocaml