Волшебные числа
В предыдущей статье была фраза о том, что числа тоже являются функциями и что такое 1 = () =› {}. Итак, давайте копнем немного дальше. Если один — функция, то что тогда два? Предположим, что это функция функции, например
one = () => {}
two = () => () => {}
// which means
two_ = () => one
Проще говоря, здесь цифра — это количество толстых стрелок. Так что ноль это ничто. Один — это одна нулевая глубина, два — две глубины и так далее. Если да, давайте определим основные операции над числами. Приращение должно быть оборачивающим числом в функцию, а уменьшение просто вызывает «числовую функцию». Нам также нужно сравнение с 0, но это легко. Ноль — это ничто, а другие числа — это что-то.
const one = () => {};
const inc = n => () => n;
const dec = n => n();
const if_zero = n => !n;
Еще нужны какие-то утилиты только для вывода результата на экран, но для самого расчета они не нужны, так что без комментариев.
const success = (n, f, acc) =>
n ? success(dec(n), f, f(acc)) : acc;
const toJS = n => success(n, x => x + 1, 0);
const print = n => console.log(toJS(n));
Арифметика
Когда у нас есть числа, декремент и приращение, мы можем определить сложение. Сложить два числа означает увеличить одно из них столько раз, сколько можно уменьшить другое.
// x + y = (x + 1) + (y - 1) const add = (x, y) => if_zero(y) ? n : add(inc(x), dec(y));
Забыл упомянуть, что здесь мы реализуем систему положительных целых чисел, но это просто для простоты.
Вычитание точно такое же, как сложение, за исключением того, что есть два уменьшения.
const sub = (n, m) => if_zero(m) ? n : sub(dec(n), dec(m));
Умножение и деление немного сложнее, но все же просто, если вы помните, что умножение означает просто прибавление первого множителя к самому себе столько раз, что вы можете уменьшить второй множитель, а деление — это просто подсчет того, сколько раз вы можете вычесть делитель из делимого.
const mul = (n, m, acc=0) =>
if_zero(n)
? acc
: mul(dec(n), m, add(acc, m));
const div = (n, m, acc=0) =>
if_zero(n)
? acc
: div(sub(n, m), m, inc(acc));
Создать функцию без аккумулятора вполне возможно, но для примера это не важно. Это здесь просто для краткости.
Теперь мы можем проверить, работает ли он. У нас есть четыре основных арифметических операции, и мы можем преобразовывать числа туда и обратно из представления JavaScript в наше.
const two = add(one, one); // 1 + 1 = 2 const three = add(one, two); // 1 + 2 = 3 const four = add(three, one); // 3 + 1 = 4 const two2 = sub(three, one); // 3 - 1 = 2 const six = mul(two, three); // 2 * 3 = 6 const three2 = div(six, two); // 6 / 2 = 3
А как насчет еще более сложных операций, таких как экспоненты, корни и т.д. Они не такие сложные, вам просто нужно использовать уже созданный базовый и еще больше расширить его.
Сравнение
Одна фундаментальная вещь, которую мы упустили в нашей реализации, — это сравнение. Чтобы сравнить два числа, нам просто нужно пересчитать оба аргумента и посмотреть, какое из них первым станет нулем.
const compare = (LEFT, RIGHT) => {
if(if_zero(LEFT) && if_zero(RIGHT)){
return 'equal';
} else if (if_zero(LEFT)){
return 'smaller';
} else if (if_zero(RIGHT)){
return 'bigger';
} else {
return equal(dec(LEFT), dec(RIGHT));
}
}
Итак, в этой части мы доказали, что можно построить систему счисления, основанную исключительно на функциях. Но это был довольно наивный подход, и чтобы сделать эту систему полной, нам нужно начать с чего-то другого. Числа на самом деле не являются основными. В компьютерном мире каждое число представлено в виде цепочки битов. На самом деле это цепочка логических значений. И если вы думаете об этом, вся информация в компьютерном мире хранится в цепочке логических значений. Итак, давайте начнем с нуля с самого BOOlean.
логический
Здесь нужно немного вернуться к передаче сообщений, о которой мы говорили в статье о функциональном представлении объектов. Там мы использовали строку в качестве сообщения, но на самом деле было бы намного проще, если бы вместо этого мы использовали функцию. И теперь мы собираемся создавать сообщения таким образом.
Сначала об утверждении «если». Он должен состоять из трех частей: «предикат», «затем» закрытие и «иначе» закрытие. Все они являются функциями, и если это так, мы могли бы определить условие как:
const IF = (predicate, left, right) => predicate(left, right);
Предикат должен быть вызван и решить, что вызывать дальше. А если так, то предикаты «истина» и «ложь» просты. Один из них всегда возвращает замыкание «тогда», а другой всегда возвращает «иначе».
const TRUE = (left, right) => left; const FALSE = (left, right) => right; IF(TRUE, 'true', 'false') // returns true IF(FALSE, 'true', 'false') // false
Можем ли мы определить логические операции над нашими «истинными» и «ложными»? Конечно. Например «и».
const AND = (left, right) =>
IF(left, IF(right, TRUE, FALSE), FALSE);
Единственное, что лучше изменить прямо сейчас, это начать использовать «каррирование». Это сделало бы правила более краткими и их было бы легче комбинировать. Если вы не знаете, что это значит, это просто. Это просто заставить функцию принимать все аргументы один за другим, вот так.
const add = (x, y, z) => x + y + z; const curried_add = x => y => z => x + y + z;
Теперь вернемся к булевым значениям. Добавим немного карри и еще пару правил.
const IF = predicate => THEN => ELSE => predicate(THEN)(ELSE);
const TRUE = THEN => ELSE => THEN;
const FALSE = THEN => ELSE => ELSE;
const AND = left => right => left(right)(FALSE);
const OR = left => right => left(TRUE)(right);
const NOT = predicate => THEN => ELSE => predicate(ELSE)(THEN);
console.log(
IF(NOT(FALSE))('true')('false') // true
);
Понимаете? Правила стали намного чище.
Номера два
Теперь мы готовы реализовать числа. Обычно «ноль» равен «false», начнем с этого факта.
const ZERO = _ => x => x; // Actually could be written as 'const ZERO = FALSE;'
Как насчет набора текста? Здесь как-то иначе, потому что все основано на единственном типе — функции. И имена переменных тоже не так важны, поскольку функция может использоваться всякий раз, когда передается структура функции. Такие функции иногда называют комбинаторами. Так что дело только в порядке звонков. И помните, все функции теперь каррированы.
Такие функции иногда называют комбинаторами. Например:
х => х — это комбинатор. x =› x(x) — это M комбинатор, и их гораздо больше.
Как будут выглядеть другие числа в этой системе? Помните, что мы полагаемся на то, насколько глубоко спрятана основная ценность. А здесь «ноль» означает «функция «f» была вызвана в ноль раз на «x»». Таким образом, «один» автоматически означает, что «f» нужно вызвать один раз, два — дважды и так далее.
const ZERO = fn => x => x; const ONE = fn => x => fn(x); const TWO = fn => x => fn(fn(x));
Однако делать все цифры заранее — не лучшая идея. Итак, нам нужно создать функцию, которая будет принимать число и возвращать следующее число, заключая его в вызов функции, поскольку ранее у нас была функция приращения. Назовем его преемником.
const SUCCESSOR = num => fn => x => fn(num(fn)(x));
Теперь мы могли легко построить числа, заменив предыдущий.
const one = SUCCESSOR(ZERO); const two = SUCCESSOR(one); const three = SUCCESSOR(two);
Чтобы проверить, как это работает, нам нужно преобразовать наши числа в представление JavaScript. Для этого просто вызовите «+1» число раз на «0»
const TO_JS = n => n(x => x + 1)(0);
Для сложения нам не понадобится сравнение с нулем, но все же определим его.
const IS_ZERO = num => num(_ => FALSE)(TRUE);
Если это ноль, то возвращается начальное значение «ИСТИНА», в противном случае возвращается значение переданной функции, которая всегда возвращает «ЛОЖЬ».
Теперь вернемся к математике. Дополнение простое.
N + M = N-кратное увеличение M
который:
const ADD = n => m => n(SUCCESSOR)(m);
«n» раз применяется преемник, наша функция приращения, к «m». Что дает нам возможность суммировать числа.
Вы заметили, насколько это стало просто по сравнению с наивным подходом, который мы использовали раньше?
const one = SUCCESSOR(ZERO);
const two = SUCCESSOR(one);
const three = ADD(one)(two);
console.log('--->', TO_JS(three)); // 3
Что уж говорить о других операциях. Начнем с умножения и показателя степени. Теперь они удивительно элегантны. Умножение — это «сочинение», просто перенос одного числа в другое.
const compose = f => g => x => f(g(x)); const MULT = compose;
А pow еще проще.
const POW = n => m => n(m);
Как насчет вычитания, деления и сравнения чисел. Они же простые.
"x" меньше или равно "y", когда "x - y ≤ 0".
"x" равно "y", когда "x ≤ y и y ≤ x".
Вычитание то же, что и сложение, только вместо приращения используйте декремент.
const LE = x => y => IS_ZERO(SUB(x)(y)) const EQ = x => y => AND(LE(x)(y))(LE(y)(x)) const SUB = x => y => y(PREDECESSOR)(x)
Единственная маленькая оговорка, что у нас пока нет того ПРЕДШЕСТВА. Это не полная наука о ракетах, нам просто нужно смотреть на число как на минус, парная структура, о которой мы говорили в предыдущей статье, но сейчас это определенно слишком.
Результатом статьи является понимание того, что если у вас есть только функции, вы можете выразить любой алгоритм. И даже более того, сначала это может показаться страшным, но на самом деле это не так страшно, как реализовать это на ассемблере.
И, кстати, настоящее имя мастера Фу было Алонзо. А на самом деле их было больше, просто погуглите «лямбда-исчисление» и просветитесь ;)
