Нерекурсивная факторная функция лямбда-исчисления
Как написать факториальную функцию без использования рекурсии с использованием лямбда-исчисления? Это означает только математическую запись, а не реализацию в каком-либо конкретном языке программирования.
2 ответа
Если под "без использования рекурсии" вы имеете в виду без общей рекурсии и, следовательно, без фиксированных точек (или собственных приложений), мы можем просто наблюдать, что факториальная функция является примитивно-рекурсивной (то есть итеративной, по сути), и существует очень общее и простое кодирование примитивной рекурсии с помощью итерации (предоставленной церковными цифрами) и пар. Я буду обсуждать общий случай, который весьма поучителен. Пусть
<M,N> = λz. z M N
fst = λp. p (λxy.x)
snd = λp. p (λxy.y)
Предположим, что у нас есть примитивно-рекурсивное определение (без параметров, для простоты)
f(0) = a
f(x+1) = h(x,f(x))
где а и ч уже определены.
Общая идея состоит в том, чтобы использовать вспомогательную функцию f', где
f'(x) = <x,f(x)>
Итак, f'(0) = < 0, a>, и, учитывая пару p =
Подводя итог,
next = λp.< succ (fst p), p h>
Наконец, чтобы вычислить f(n), нам нужно итерировать следующую функцию n раз, начиная с <0, a>, а затем взять второй компонент:
f = λn. snd (n next <0,a>)
я ничего не сказал, я не имел в виду
Под "без использования рекурсии" вы должны понимать "без функции, вызывающей себя по имени "
В любом случае, давайте напишем факториал
fact := λn. zero? n one (mult n (fact (dec n)))Теперь нас не особо волнует zero?, mult, dec, или даже one в этом примере; Вы можете реализовать их по своему усмотрению - мы просто хотим убрать выделенную жирным шрифтом рекурсию по имени,
... fact (dec n)Самый простой способ сделать это - применить лямбду к себе - познакомьтесь с комбинатором U
U := λf. f f
Теперь мы можем обернуть наше оригинальное выражение в лямбду и применить U
fact := U (λf. λn. zero? n one (mult n (??? (dec n))))Но что мы ставим на место fact??? - Напомним, что f является ссылкой на саму внешнюю лямбду, поэтому для того, чтобы это было тем же случаем в следующей "итерации", мы должны применить f сам по себе, как и U - на самом деле, вы можете думать о U как о некоем зеркале, и ваша функция может отражаться обратно в это зеркало для повторения; только на этот раз, без использования имени ^_^
fact := U (λf. λn. zero? n one (mult n (f f (dec n))))Да, да, но еще более проницательный заметит, что вы можете использовать зеркало (U) прямо внутри лямбды.
fact := U (λf. λn. zero? n one (mult n (U f (dec n))))расширен без U
Мы знаем, как расширить внутреннее - мы написали это так в первый раз
fact := U (λf. λn. zero? n one (mult n (f f (dec n))))Теперь разверните внешний U
fact := (λf. λn. zero? n one (mult n (f f (dec n)))) (λf. λn. zero? n one (mult n (f f (dec n))))это работает?
все церковные цифры представлены как #N
fact := U λf. λn. zero? n #1 (mult n (U f (dec n)))
fact #4
U (λf. λn. zero? n #1 (mult n (U f (dec n))) #4
(λf. f f) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4
(λf. λn. zero? n #1 (mult n (U f (dec n))) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4
(λn. zero? n #1 (mult n (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec n))) #4
zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))
zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))
// (zero? #4); false; returns second argument
(mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))
// which is #4 * ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4))
// which is ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) #3)
// which is equivalent to...
fact #3
// so ...
(mult #4 (fact #3))
// repeating this pattern ...
(mult #4 (mult #3 (fact #2))
(mult #4 (mult #3 (mult #2 (fact #1)))
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0))))
(mult #4 (mult #3 (mult #2 (mult #1 #1))))
(mult #4 (mult #3 (mult #2 #1)))
(mult #4 (mult #3 #2))
(mult #4 #6)
#24
демонстрация в JavaScript
Идите вперед и посмотрите на мощь U комбинатора своими собственными глазными яблоками!
const U =
f => f (f)
const fact =
U (f => n =>
n === 0 ? 1 : n * U (f) (n - 1))
console.log (fact (4)) // 24И снова как чистое лямбда-выражение
console.log (
(f => n => n === 0 ? 1 : n * f (f) (n - 1))
(f => n => n === 0 ? 1 : n * f (f) (n - 1))
(4)
) // 24взаимная рекурсия
Приведенный выше фрагмент демонстрирует очень важное свойство этого рекурсивного процесса: он является взаимно рекурсивным. Как видите, на самом деле есть две (хотя и одинаковые) функции, управляющие рекурсией; A вызывает B, B вызывает A - Однако в случае U-комбинатора есть только одна функция, которая применяется к себе, так что она фактически разрешает прямую рекурсию - лямбда вызывает сам себя, используя свой параметр, а не имя (у лямбд нет имени для звонка)
Y?
U-комбинатор немного громоздок, потому что он ожидает, что пользователь "отразит" функцию, чтобы повторить - что если бы мы могли снабдить внешнюю лямбду функцией, которая является самим зеркалом?
U := λf. f f
Y := λg. U (λf. g (U f))
Я снова покажу вам то же определение, но в двух строках, чтобы вы могли видеть "зеркала" и их положение.
/ g, user's function
/
/ / outer reflection
/ /
Y := λg. U (λf. ... )
g (U f)
\
\ call g with inner reflectionТак что теперь, когда вы подаете заявление Y для любой лямбды (g) ее параметр становится функцией для вычисления самой лямбды - изменение fact в
fact := Y (λf. λn. zero? n one (mult n (f (dec n))))расширяя Y
Y := λg. U (λf. g (U f)) // expand inner U
Y := λg. U (λf. g (f f)) // expand outer U
Y := λg. (λf. g (f f)) (λf. g (f f))какое определение вы видите в википедии; просто переименованный
у меня только что было глубокое открытие
Получив Y из U выше, я увидел нечто, чего я никогда раньше не видел - скрытый B
Y := λg. U (λf. g (U f))
B := λf. λg. λx. f (g x)
Y' := λg. U (B g U)
Одна из самых красивых вещей, которые я когда-либо видел - и это тоже работает; не то чтобы у нас была какая-то причина думать, что это не будет...
#lang lazy
(define B (λ (f)
(λ (g)
(λ (x)
(f (g x))))))
(define U (λ (f)
(f f)))
(define Y (λ (g)
(U ((B g) U))))
(define fact (Y (λ (f)
(λ (n)
(if (= n 0)
1
(* n (f (sub1 n))))))))
(fact 4) ;; 24
Haskellers
Вы когда-нибудь видели Y, выраженную как?
Y = U . (. U)
where U f = f f