您将如何在F＃中实现定点操作员（Y Combinator）？

Question

我正在使用f＃创建一个lambda演算。目前，我被困在试图弄清楚如何实现定点操作员（也称为Y Combinator）。

我认为其他一切都在井井有条。表达式由以下歧视联盟表示：

type Expr =
 | Const of int
 | Plus  of Expr * Expr
 | Times of Expr * Expr
 | Minus of Expr * Expr
 | Div   of Expr * Expr
 | Neg   of Expr
 | Var   of string
 | Fun   of string * Expr
 | App   of Expr * Expr
 | If    of Expr * Expr * Expr

我的 eval 功能似乎有效。以下示例都产生了预期的结果。
示例1：
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
示例2：
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
示例3：
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

但是正如我提到的那样，我很难在lambda演算中实现定点操作员。它是定义的 这里 作为：
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

有没有人有什么建议？我查看了有关Y组合者的其他问题，但找不到我能成功采用的任何问题。

所有帮助都得到赞赏。

编辑： 修复了代码中的错字...以前我 Mult 代替 Minus 在歧视联盟中。有趣的是，我只是注意到了！

Answer 1

您所指的版本仅适用于懒惰的语言，如果您的语言不使用懒惰的评估策略，您将陷入无限循环中。尝试翻译此：

Y = lambda G. (lambda g. G(lambda x. g g x)) (lambda g. G(lambda x. g g x))

Answer 2

据我所记得的，在未型的lambda微积分中，有整个Y组合者，但是如果您的语言被严格键入，尽管人们试图在ML和F＃中进行特殊案例，但很难实施一种。如果您的语言支持递归（lambda conculus却没有），似乎并不是很有用。看看关于该主题的讨论，Stackoverflow看到了通用的“功能编程”或ML的标记，我认为有一些见解：

Y-Combinator实践示例