Доброго дня, друзья!
Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.
Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка JavaScript, а именно, будем использовать только анонимные функции от одного аргумента. Больше нам ничего не потребуется (ну почти).
Начнем с определения факториала, и посмотрим, что нам понадобится в процессе решения задачи:
Итак, нам потребуются функции, логические значения (для результата операции сравнения с нулем), условный оператор, операции умножения и вычитания единицы, кроме того нужно будет реализовать рекурсивный вызов функции.
Готовы?
Начнем с простого, с логических значений True, False и функции If. True и False представлены каррированными функциями двух аргументов осуществляющими выбор первого либо второго аргумента. True выбирает первый аргумент, а False — второй. If принимает три аргумента, логическое значение, ветку then и ветку else.
Можно побаловаться в консоли выполняя код типа:
Дальше нам потребуются числа. Множество натуральных чисел можно получить определив значение числа НОЛЬ и операцию ПЛЮС_ОДИН. Числа Чёрча, грубо говоря, представляют собой функции двух аргументов, применяющие первый аргумент ко второму n раз, где n — это соответствующее натуральное число.
Дополнительно определим предикат проверяющий, является ли число нулем, реализация факториала потребует такую проверку. Предикат возвращает False если первый аргумент числа выполнился хотя бы раз.
Проверьте как работают числа:
Как видите, к нулю трижды прибавилась единица, а предикат корректно распознает переданное число.
Теперь, когда у нас есть все натуральные числа определим функцию умножающую два числа, результат умножения — это функция, которая n раз по m раз применяет свой аргумент.
Осталось научиться отнимать единицу от числа. Тут все немного сложнее. Идея вычитания состоит в том, что строится пара чисел (n, n — 1) и берется второй элемент пары. Таким образом нам нужно получить конструктор пары, а так же функции получения первого и второго элемента. После чего мы сможем определить функцию получения предыдущего числа.
Поиграемся с парами и вычитанием:
Казалось бы, все уже готово и можно реализовать факториал:
Но есть две проблемы, первая заключается в том, что JavaScript — язык с аппликативным порядком вычислений и наш факториал просто повиснет, т.к. будет выполнять рекурсивный вызов вне зависимости от значения аргумента. Эту проблему легко решить обернув рекурсивный вызов в анонимную функцию и тем самым отложив выполнение.
Теперь функция работает корректно:
Осталась последняя проблема. Вначале я обещал использовать только анонимные функции, а тут мы видим рекурсивный вызов по имени fact. Нужно от него избавиться и в этом нам поможет Y-комбинатор. Объяснять принцип его работы я не буду, на эту тему есть статьи и на Хабре и вне пределов Хабра. Рекомендую например вот эту блогозапись. Y-комбинатор в аппликативном языке выглядит так:
Проверить корректность его работы можно так:
Теперь подставим факториал в Y-комбинатор и получим конечный вариант:
Для большего удобства определим функции NatToChurch и ChurchToNat:
Теперь можно ставить эксперименты в консоли:
Последний шаг, сделать все подстановки и получить финальную функцию:
Осталось ответить на вопрос «Зачем так делать?». Признаюсь честно, на этот вопрос у меня ответа нет. Всем добра!
Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.
Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка 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);
};
});
Осталось ответить на вопрос «Зачем так делать?». Признаюсь честно, на этот вопрос у меня ответа нет. Всем добра!