Вычисление факториала на числах Чёрча
Доброго дня, друзья! Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.
Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка JavaScript, а именно, будем использовать только анонимные функции от одного аргумента. Больше нам ничего не потребуется (ну почти :)).
Начнем с определения факториала, и посмотрим, что нам понадобится в процессе решения задачи:
var fact = function (n) { if (n === 0) return 1; return n * fact (n — 1); }; Итак, нам потребуются функции, логические значения (для результата операции сравнения с нулем), условный оператор, операции умножения и вычитания единицы, кроме того нужно будет реализовать рекурсивный вызов функции.
Готовы? Начнем с простого, с логических значений True, False и функции If. True и False представлены каррированными функциями двух аргументов осуществляющими выбор первого либо второго аргумента. True выбирает первый аргумент, а False — второй. If принимает три аргумента, логическое значение, ветку then и ветку else.
var True = function (x) { return function (y) { return x; }; };
var False = function (x) { return function (y) { return y; }; };
var If = function (p) { return function (t) { return function (e) { return p (t)(e); } }; }; Можно побаловаться в консоли выполняя код типа:
console.log (If (True)('foo')('bar')); console.log (If (False)('foo')('bar')); Дальше нам потребуются числа. Множество натуральных чисел можно получить определив значение числа НОЛЬ и операцию ПЛЮС_ОДИН. Числа Чёрча, грубо говоря, представляют собой функции двух аргументов, применяющие первый аргумент ко второму n раз, где n — это соответствующее натуральное число.
var Zero = function (f) { return function (x) { return x; }; };
var Succ = function (n) { return function (f) { return function (x) { return f (n (f)(x)); }; }; }; Дополнительно определим предикат проверяющий, является ли число нулем, реализация факториала потребует такую проверку. Предикат возвращает False если первый аргумент числа выполнился хотя бы раз.
var IsZero = function (n) { return n (function (x) { return False; })(True); }; Проверьте как работают числа:
Succ (Succ (Succ (Zero)))(function (x) { return x + 1; })(0); console.log (If (IsZero (Zero))('zero')('not zero')); console.log (If (IsZero (Succ (Zero)))('zero')('not zero')); Как видите, к нулю трижды прибавилась единица, а предикат корректно распознает переданное число.
Теперь, когда у нас есть все натуральные числа определим функцию умножающую два числа, результат умножения — это функция, которая n раз по m раз применяет свой аргумент.
var Mul = function (n) { return function (m) { return function (f) { return n (m (f)); }; }; }; Осталось научиться отнимать единицу от числа. Тут все немного сложнее. Идея вычитания состоит в том, что строится пара чисел (n, n — 1) и берется второй элемент пары. Таким образом нам нужно получить конструктор пары, а так же функции получения первого и второго элемента. После чего мы сможем определить функцию получения предыдущего числа.
var Pair = function (a) { return function (b) { return function (t) { return t (a)(b); }; }; };
var Fst = function (p) { return p (True); };
var Snd = function (p) { return p (False); };
var Pred = function (n) { return function (s) { return function (z) { return Snd (n (function (p) { return Pair (s (Fst (p)))(Fst (p)); })(Pair (z)(z))); }; }; }; Поиграемся с парами и вычитанием:
Fst (Pair ('foo')('bar')); // => «foo» Snd (Pair ('foo')('bar')); // => «bar» Pred (Succ (Succ (Zero)))(function (x) { return x + 1; })(0); // => 1 Казалось бы, все уже готово и можно реализовать факториал:
var fact = function (n) { return If (IsZero (n))(Succ (Zero))(Mul (n)(fact (Pred (n)))); }; Но есть две проблемы, первая заключается в том, что JavaScript — язык с аппликативным порядком вычислений и наш факториал просто повиснет, т.к. будет выполнять рекурсивный вызов вне зависимости от значения аргумента. Эту проблему легко решить обернув рекурсивный вызов в анонимную функцию и тем самым отложив выполнение.
var fact = function (n) { return If (IsZero (n))(Succ (Zero))(function (x) { return Mul (n)(fact (Pred (n)))(x); }); }; Теперь функция работает корректно:
fact (Succ (Succ (Succ (Zero))))(function (x) { return x + 1; })(0); // => 6 Осталась последняя проблема. Вначале я обещал использовать только анонимные функции, а тут мы видим рекурсивный вызов по имени fact. Нужно от него избавиться и в этом нам поможет Y-комбинатор. Объяснять принцип его работы я не буду, на эту тему есть статьи и на Хабре и вне пределов Хабра. Рекомендую например вот эту блогозапись. Y-комбинатор в аппликативном языке выглядит так:
var Y = function (f) { return function (x) { return x (x); }(function (x) { return function (y) { return f (x (x))(y); }; }); }; Проверить корректность его работы можно так:
Y (function (f) { return function (n) { return If (IsZero (n))(Succ (Zero))(function (x) { return Mul (n)(f (Pred (n)))(x); }); }; })(Succ (Succ (Succ (Zero))))(function (x) { return x + 1; })(0); // => 6 Теперь подставим факториал в Y-комбинатор и получим конечный вариант:
var fact = function (x) { return x (x); }(function (x) { return function (y) { return function (f) { return function (n) { return If (IsZero (n))(Succ (Zero))(function (x) { return Mul (n)(f (Pred (n)))(x); }); }; }(x (x))(y); }; }); Для большего удобства определим функции NatToChurch и ChurchToNat:
var NatToChurch = function (n) { return n == 0? Zero: function (f) { return function (x) { return f (NatToChurch (n — ChurchToNat (Succ (Zero)))(f)(x)); }; }; };
var ChurchToNat = function (n) { return n (function (x) { return x + 1; })(0); }; Теперь можно ставить эксперименты в консоли:
ChurchToNat (fact (NatToChurch (5))); // => 120 Последний шаг, сделать все подстановки и получить финальную функцию:
Осторожно, очень много функций var fact = function (x) { return x (x); }(function (x) { return function (y) { return function (f) { return function (n) { return function (p) { return function (t) { return function (e) { return p (t)(e); } }; }(function (n) { return n (function (x) { return function (x) { return function (y) { return y; }; }; })(function (x) { return function (y) { return x; }; }); }(n))(function (n) { return function (f) { return function (x) { return f (n (f)(x)); }; }; }(function (f) { return function (x) { return x; }; }))(function (x) { return function (n) { return function (m) { return function (f) { return n (m (f)); }; }; }(n)(f (function (n) { return function (s) { return function (z) { return function (p) { return p (function (x) { return function (y) { return y; }; }); }(n (function (p) { return function (a) { return function (b) { return function (t) { return t (a)(b); }; }; }(s (function (p) { return p (function (x) { return function (y) { return x; }; }); }(p)))(function (p) { return p (function (x) { return function (y) { return x; }; }); }(p)); })(function (a) { return function (b) { return function (t) { return t (a)(b); }; }; }(z)(z))); }; }; }(n)))(x); }); }; }(x (x))(y); }; }); Осталось ответить на вопрос «Зачем так делать?». Признаюсь честно, на этот вопрос у меня ответа нет. Всем добра!
