Как бы вы реализовали оператор с фиксированной точкой (Y combinator) в F #?

Question

Я использую F # для создания лямбда-исчисления.В настоящее время я застрял, пытаясь понять, как бы я реализовал оператор с фиксированной точкой (также называемый 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

Но, как я уже упоминал, у меня возникли трудности с реализацией оператора с фиксированной точкой в моем лямбда-исчислении.Это определено здесь как:
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

У кого-нибудь есть какие-нибудь предложения?Я просмотрел другие вопросы, касающиеся Y combinator, но не смог найти ничего, что я смог бы успешно внедрить.

Мы ценим любую помощь.

Редактировать: Исправлена опечатка в коде...раньше у меня было 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

Насколько я помню, в нетипизированном лямбда-исчислении существует целый класс Y-комбинаторов, но реализовать даже один из них становится сложно, если ваш язык строго типизирован, хотя люди пытались делать особые случаи в ML, а также в F #.Кажется, это не очень полезно, если ваш язык поддерживает рекурсию (чего нет в лямбда-исчислении).Взгляните на обсуждения по этой теме, которые Stackoverflow видел помеченными как generic "функциональное программирование" или ML, я думаю, что можно получить некоторые идеи:

Практический пример Y-Комбинатора