Кто-нибудь может на пальцах объяснить что такое y-комбинатор в λ-исчислении?
-
3Наверное он еще сможет объяснить, что такое монада в двух словах...– user786067024 апр 2018 в 14:54
-
Для вопросов касательно чисто математики есть сайт math.stackexchange.com того же сообщества. Он правда на английском. Здесь форум программистов. Врядли кого интерисует здесь тема комбинаторов.– nick_n_a24 апр 2018 в 14:55
-
Понять монады так же просто, как бросить курить. Я делал это много раз.– Alexander Petrov24 апр 2018 в 18:38
2 ответа
Комбинатор - это элементарная функция высшего порядка. "Элементарная" означает что эта функция предназначена для того чтобы строить на ее основе другие функции; в некоторых системах аксиом комбинаторы считаются неделимыми.
"Высшего порядка" означает что функция принимает или возвращает не скалярное значение, а другую функцию.
Неподвижная точка - это термин из матанализа, он означает такую точку x0 что f(x0) = x0 (у каждой функции свои неподвижные точки).
Таким образом, комбинатор неподвижной точки - это элементарная функция высшего порядка, которая ищет для указанной функции ее неподвижную точку.
С точки зрения математики, поиск неподвижной точки - это решение уравнения, довольно сложная задача. Но все меняется когда неподвижная точка ищется не у обычной функции, а у функции высшего порядка.
И так, допустим у нас есть функция f, и у нее есть неподвижная точка x:
f x = x
По определению, комбинатор неподвижной точки должен для любого f найти x:
Y f = x
Подставив второе уравнение в первое, получим
f (Y f) = Y f
Или, что то же самое,
Y f = f (Y f) = f (f (f (f (f (f (f (f (f ...))))))))
Это равенство верно для любого комбинатора неподвижной точки, но для комбинатора Y это не просто равенство, но еще и алгоритм: он именно так и работает. Разумеется, подобная бесконечная рекурсия возможно только в "ленивых" вариантах λ-исчисления.
Для чего используется этот комбинатор? Он используется для того чтобы писать рекурсивные функции в тех языках где нет другого способа это сделать.
Рассмотрим, к примеру, одну из возможных записей факториала:
fac n = if (n = 0) 1 (n * fac (n-1))
Если язык запрещает делать прямой рекурсивный вызов (обращаться к fac изнутри определения fac) - можно использовать комбинатор неподвижной точки:
fac = Y (λf . λn . if (n = 0) 1 (n * f (n-1)))
На практике так почти никто не пишет, потому что во всех нормальных языках рекурсия разрешена.
В теории же комбинатор неподвижной точки - это стандартная реализация рекурсивных вызовов.
По определению, комбинатор, который переводит свой аргумент в его неподвижную точку:
∀f . f(Y f) ≡ Y f
В лямбда-исчислении есть простая его форма для лямбда-выражений:
Y = λf . (λx . f(x x)) (λx . f(x x))
В частности, если начать проводить экспансию, то
Yf
= (λf . (λx . f(x x)) (λx . f(x x))) f
= (λx . f(x x)) (λx . f(x x))
= f(x x)|x = (λx . f(x x))
= f((λx . f(x x)) (λx . f(x x)))
= f((λf . (λx . f(x x)) (λx . f(x x))) f)
= f(Yf)
Примерно на пальцах...