Wie würden Sie einen Festpunkt-Operator (Y Combinator) in F # implementieren?

Question

Ich bin mit F # einem Lambda-Kalkül zu erstellen. Ich bin zur Zeit stecken, um herauszufinden, wie ich den Festpunkt Operator implementieren würde (auch als Y Combinator).

Ich denke, alles in Ordnung ist. Ausdrücke werden durch die folgende diskriminierte Gewerkschaft vertreten:

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

Meine eval Funktion scheint zu funktionieren. Die folgenden Beispiele alle erwarteten Ergebnisse.
Beispiel 1:
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
Beispiel 2:
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
Beispiel 3:
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

Aber wie ich schon sagte, ich habe Schwierigkeiten, den Festpunkt-Operator in meinem Lambda-Kalkül zu implementieren. Es ist definiert hier als:
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

Hat jemand irgendwelche Vorschläge? Ich habe in anderen Fragen in Bezug auf die Y Combinator sah, konnte aber nichts finden, dass ich in der Lage war, um erfolgreich zu übernehmen.

Jede Hilfe sehr geschätzt wird.

Edit: ein Fehler im Code behoben ... vorher hatte ich Mult statt Minus in der diskriminierte Vereinigung. Komisch, dass ich gerade bemerkt, dass!

Answer 1

Die Version, die Sie sich beziehen Werke nur mit einer faulen Sprache, und wenn Ihre Sprache ist eine faule Bewertungsstrategie nicht verwenden, werden Sie in einer Endlosschleife stecken. Versuchen Sie übersetzen diese:

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

Answer 2

Soweit ich mich erinnere, gibt es eine ganze Klasse von Y Combinator in nicht typisierten Lambda-Kalkül, aber es wird schwierig, auch nur ein, wenn Ihre Sprache zu implementieren ist streng typisiert, obwohl die Leute versucht haben, spezielle Fälle in ML zu tun und auch F #. Es scheint nicht sehr nützlich zu sein, wenn Sie die Sprache Rekursion unterstützt (Kalkül, die Lambda nicht). Werfen Sie einen Blick auf den Diskussionen zu diesem Thema, dass Stackoverflow hat mit generic „funktionaler Programmierung“ markiert gesehen oder ML, ich denke, es gibt einige Einblicke zu haben:

Y-Combinator Praxisbeispiel