Доброго дня, друзья!
Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.
Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка 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);
};
});
Осталось ответить на вопрос «Зачем так делать?». Признаюсь честно, на этот вопрос у меня ответа нет. Всем добра!
Автор: f0rk
