Как бы вы реализовали оператор с фиксированной точкой (Y combinator) в F #?
-
28-09-2019 - |
Вопрос
Я использую 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
в дискриминируемом союзе.Забавно, что я только сейчас это заметил!
Решение
Версия, на которую вы ссылаетесь, работает только с ленивым языком, и если ваш язык не использует стратегию ленивой оценки, вы застрянете в бесконечном цикле.Попробуйте перевести это:
Y = lambda G. (lambda g. G(lambda x. g g x)) (lambda g. G(lambda x. g g x))
Другие советы
Насколько я помню, в нетипизированном лямбда-исчислении существует целый класс Y-комбинаторов, но реализовать даже один из них становится сложно, если ваш язык строго типизирован, хотя люди пытались делать особые случаи в ML, а также в F #.Кажется, это не очень полезно, если ваш язык поддерживает рекурсию (чего нет в лямбда-исчислении).Взгляните на обсуждения по этой теме, которые Stackoverflow видел помеченными как generic "функциональное программирование" или ML, я думаю, что можно получить некоторые идеи: