Комбинатор с фиксированной запятой
-
Определение и свойства комбинатора с фиксированной точкой
- Комбинатор с фиксированной точкой — это комбинатор, который возвращает фиксированную точку функции.
- Y-комбинатор — это комбинатор с фиксированной точкой, который возвращает функцию, применяемую к самому себе.
- Z-комбинатор — это комбинатор с фиксированной точкой, который возвращает функцию, применяемую к предыдущему результату.
-
Примеры и реализация
- Y-комбинатор используется для реализации рекурсии в лямбда-исчислении.
- Z-комбинатор используется в строгих языках программирования, где применяется аппликативный порядок вычисления.
- Существуют нестандартные комбинаторы с фиксированной точкой, которые не удовлетворяют стандартному уравнению фиксированной точки.
-
Реализация на других языках
- В Haskell и других языках с отложенным вычислением можно определить комбинатор с фиксированной точкой с помощью оператора fix.
- В императивных языках, таких как Lisp, можно использовать присваивание переменной для создания комбинатора с фиксированной точкой.
-
Тип и печать
- В полиморфном лямбда-исчислении тип комбинатора с фиксированной точкой зависит от типа функции, которую он применяет.
- В просто типизированном лямбда-исчислении комбинатор Y не может быть напечатан, так как он будет иметь бесконечный тип.
-
Применение и рекурсия
- Комбинаторы с фиксированной точкой используются для описания рекурсивных вычислений и реализации анонимных рекурсивных функций.
- Y-комбинатор позволяет определить рекурсию как набор правил перезаписи, не требуя встроенной поддержки рекурсии в языке.
-
Ссылки и примечания
- Ссылки на литературу и внешние ресурсы приведены в статье.
- В статье также упоминаются анонимная функция и итерация с фиксированной точкой.
Полный текст статьи: