Комбинаторы с фиксированной точкой

Question

Я новичок в мире fixed-point combinators, и я думаю, они используются для рекурсии на анонимных лямбдах, но я действительно не использовал их или даже не смог полностью обвести вокруг себя голову.

Я видел пример в Javascript для Y-combinator, но не смог его успешно запустить.

Вопрос здесь, может кто-нибудь дать интуитивный ответ:

• Что с фиксированной точкой комбинаторов, (а не только теоретически, но и в контексте некоторого примера, чтобы показать, что именно неподвижный - точка в этом контексте)?
• Каковы другие виды комбинаторов с фиксированной запятой, кроме Y-combinator?

Бонусные очки: Если пример не только на одном языке, желательно в Clojure, а также.

UPDATE:

я смог найти простой пример Clojure, но до сих пор трудно понять саму Y-Combinator:

(defn Y [r] 
    ((fn [f] (f f)) 
    (fn [f] 
    (r (fn [x] ((f f) x)))))) 

Хотя пример лаконичен , Мне трудно понять, что происходит внутри функции. Любая предоставленная помощь будет полезна.

Answer 1

Предположим, вы хотели написать факториальную функцию. Обычно вы должны писать это как-то вроде

function fact(n) = if n=0 then 1 else n * fact(n-1) 

Но это использует явную рекурсию. Если вы хотите использовать Y-комбинатор вместо этого, вы могли бы первый абстрактный факт, как что-то вроде

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1) 

Это принимает аргумент (myFact), который он называет был «истинный» факт бы назвал себя. Я называю этот стиль функции «Y-ready», то есть он готов к подаче на Y-combinator.

Y-combinator использует factMaker для создания чего-то эквивалентного «истинному» факту.

newFact = Y(factMaker) 

Зачем беспокоиться? Две причины. Первая теоретическая: нам не нужна рекурсия, если мы можем «имитировать» ее с помощью Y-комбинатора.

Второй - более прагматичный. Иногда мы хотим обернуть каждый вызов функции некоторым дополнительным кодом для ведения журнала или профилирования или memoization или множества других вещей. Если мы попытаемся сделать это с истинным фактом, дополнительный код будет вызван только для первоначального вызова, а не для всех рекурсивных вызовов. Но если мы хотим сделать это для каждого вызова, в том числе все рекурсивный вызов, мы можем сделать что-то вроде

loggingFact = LoggingY(factMaker) 

где LoggingY представляет собой модифицированный вариант Y Combinator, который вводит регистрацию. Заметьте, что нам вообще не нужно было менять factMaker!

Все это является большей мотивацией, почему Y-комбинатор имеет значение, чем подробное объяснение того, как работает эта конкретная реализация Y (потому что существует много разных способов реализации Y).

Answer 2

Чтобы ответить на ваш второй вопрос о других, чем Y. затруднительной точки комбинаторов Есть счетно бесконечно много стандартных затруднительную точки комбинаторов, то есть, комбинаторы fix, удовлетворяющего уравнению

fix f = f (fix f) 

Есть также contably много нестандартные исправления точка комбинаторы, которые удовлетворяют уравнение

fix f = f (f (fix f)) 

и т.д. стандартных комбинатор исправления точки рекурсивно перечислимы, но нестандартные нет. См. Следующую веб-страницу для примеров, ссылок и обсуждений. http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes