[a,b].reduce(f,x) код для [a,b].reduce(f) с использованием функциональных ссылок на основе преобразователя /CPS?

Question

В моем предыдущем вопросе:

Извлечение данных из цепочки функций без массивов

@Aadit M Shah дал мне удивительное решение следующим образом:

/questions/7959932/izvlechenie-dannyih-iz-tsepochki-funktsij-bez-massivov/7959947#7959947

Учитывая выражение как A(a)(b)(f) где f это функция, невозможно знать, f должен быть добавлен в список или это функция сокращения. Следовательно, я собираюсь описать, как писать выражения, как A(a)(b)(f, x) что эквивалентно [a, b].reduce(f, x) , Это позволяет нам различать, когда список заканчивается, в зависимости от того, сколько аргументов вы предоставили:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L(k => g((f, a) => k(f, f(a, x))));
    case 2: return g((f, a) => a)(x, a);
    }
};

const A = L(x => x);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

Работает за счет продолжения. Каждый раз, когда мы добавляем новый элемент, мы накапливаем функцию CPS. Каждая функция CPS вызывает предыдущую функцию CPS, тем самым создавая цепочку функций CPS. Когда мы даем этой цепочке функций CPS базовую функцию, она разворачивает цепочку и позволяет нам ее уменьшить. Та же идея стоит за преобразователями и линзами.

Для меня осталось 2 вопроса.

1. Чтобы отличить сокращающую функцию, я рассмотрю некоторый пользовательский механизм набора текста с использованием отражения, но для того, чтобы сосредоточиться на этом вопросе, пока я хотел бы просто применить

   const isReducer = f => (typeof f === 'function');

2. Требование предоставить начальное значение имеет предел для сворачивания / уменьшения, например, невозможно обеспечить начальное значение для бинарных операций для уменьшения, такого как

   const head = (a, b) => a; const tail = (a, b) => b;

(если вы не укажете первое / последнее значение вручную, что не имеет смысла запускать код) Теоретически, каждая двоичная операция имеет значение идентификатора, но что-то невозможно предоставить как есть. Единственный способ - абстрагироваться как личность.

Сказав это, я не могу реорганизовать предоставленный код в одиночные аргументы и по типу функции-редуктора, а также по умолчанию в качестве начального значения последовательности.

Можете ли вы предоставить переработанный код? Также приветствуется любая информация о преобразователе / ​​CPS для этого примера.

Answer 1

Когда вы не предоставляете начальную стоимость, вы теряете много энергии. Например, вы не сможете преобразовать список в массив. Это связано с тем, что возвращаемый тип должен соответствовать типу элементов списка. Рассматривать:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs

Как видите, тип возвращаемого значения foldl может быть любого типа b который не зависит от типа a, Тем не менее, тип возвращаемого значения foldl1 вынужден быть a, Следовательно, если у вас есть список A(1)(2)(3)(4)(5) тогда, когда вы свернете этот список, результатом обязательно должен быть номер.

Вы можете сойти с рук, сделав что-то вроде A(1)(2)(3)(4)(5)(concat2) где const concat2 = (x, y) => [].concat(x, y) потому что JavaScript не является строго типизированным языком. Тем не менее, это не соответствует, потому что A([1,2,3])([4,5,6])([7,8,9])(concat2) оценивает [1,2,3,4,5,6,7,8,9] вместо [[1,2,3],[4,5,6],[7,8,9]], Я не вижу способа преобразовать второй список в массив при сохранении его структуры, если у вас нет начального значения.

---

Тем не менее, если вы все еще хотите это сделать, вам мало что придется изменить. Заметить, что foldl1 только делегаты работают foldl, Следовательно, нам просто нужно отделить первый элемент списка от остальных и использовать его в качестве начального значения аккумулятора:

const L = g => a => x => typeof x !== "function" ?
    L((f, a) => f(g(f, a), x))(a) :
    g(x, a);

const A = L((f, a) => a);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y)); // 15
console.log(xs((x, y) => x * y)); // 120

Наконец, если вы действительно хотите узнать о функциональном программировании и продолжениях, тогда я предлагаю вам прочитать SICP (Структура и интерпретация компьютерных программ) или HtDP (Как разрабатывать программы). HtDP обычно считается более удобным для начинающих. Тем не менее, я настоятельно рекомендую прочитать SICP.

Answer 2

@Aadit M Shah

Когда вы не предоставляете начальную стоимость, вы теряете много энергии. Например, вы не сможете преобразовать список в массив. Это связано с тем, что возвращаемый тип должен соответствовать типу элементов списка.

Я думаю, что это не так. На самом деле, в алгебре определение моноидов не требует такого начального значения.

Если быть точным, начальное значение в программировании - это элемент Identity, который предоставляет ваш собственный код (см. Мой код для пояснения).

Класс определяется бинарным оператором, и бинарный оператор несет полную ответственность за сопоставление возвращаемого значения с тем же классом.

Даже для массива, concat операция может быть реорганизована, как показано ниже, а непредоставление начальных значений даже дает firstlast бинарные операции, которые вы не можете записать как конкретное значение, и ваш исходный код уже предоставил начальное значение, очень правильно, как id: x => x!

//type system
const typedPrimitive = T => i => {
    const typeProperty = {
        enumerable: false,
        configurable: false,
        writable: false,
        value: true
    };
    const derived = Object(i);
    Object.setPrototypeOf(derived, Object(i));
    Object.defineProperty(derived, T, typeProperty);
    return derived;
};

const typedObject = T => i => {
    const handler = {
        get: (target, name) => name == T//must ==
            ? true : target[name]
    };
    return new Proxy(i, handler);
};

const typed = T => i => (i !== Object(i))//primitives
    ? typedPrimitive(T)(i)
    : typedObject(T)(i)

const istype = T => i => i[T] === true;

const Type = T => i => (i === T) || (i == null)
    ? i
    : typed(T)(i);

const isType = T => i => (i === T)
    ? true
    : (i == null)
        ? false
        : istype(T)(i);

const freeOp = f => Type(freeOp)(f);

//======================

const _L = g => a => b => isType(freeOp)(b)
    ? g((f, a) => a)(b, a)
    : _L(k => g((f, a) => k(f, f(a, b))))(a);

const id = x => x;
const L = _L(id);

const add = (x, y) => Number(x) + Number(y);
const multiply = (x, y) => Number(x) * Number(y);

const unit = (a) => [a];
const join = ([a]) => [].concat(a);
const flatUnit = a => join(unit(a));
const concat = (a, x) => flatUnit(a)
    .concat(x);

const addArray = (a, b) => {
    const aa = isType(addArray)(a)
        ? a : [a];
    return Type(addArray)([...aa, b]);
};

const concatStr = (a, x) => String(a) + String(x);

const max = (a, b) => (a > b) ? a : b;
const min = (a, b) => (a < b) ? a : b;

const first = (a, b) => a;//???
const last = (a, b) => b;

const io = (a, b) => {
    log("a:" + a);
    log("b:" + b);
    return b;
};

log(
    L(1)(2)(3)(4)(5)(freeOp(add))
); // 15
log(
    L(1)(2)(3)(4)(5)(freeOp(multiply))
); // 120
log(
    L(1)(2)(3)(4)(5)(freeOp(concatStr))
); // 12345
log(
    L(1)(2)(3)(4)(5)(freeOp(concat))
); // [ 1, 2, 3, 4, 5 ]
log(
    L([1, 2])([3, 4])([5, 6])([7, 8])([9])(freeOp(concat))
);
log(
    L([1, 2])([3, 4])([5, 6])([7, 8])([9])(freeOp(addArray))
); // [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], [ 7, 8 ], [ 9 ] ]
log(
    L(1)(2)(3)(4)(5)(freeOp(max))
); // 5
log(
    L(1)(2)(3)(4)(5)(freeOp(min))
); // 1
log(
    L(1)(2)(3)(4)(5)(freeOp(first))
); // 1
log(
    L(1)(2)(3)(4)(5)(freeOp(last))
); // 5

log(//IO Monoid
    L(1)(2)(3)(4)(5)(freeOp(io))
); // 5


function log(m) {
    console.log((m)); //IO
    return m;
};

Замечания: Type изменяет исходное значение, поэтому для того, чтобы сделать его неизменным, необходимо выполнить рефакторинг для использования Proxy/Reflection в ES6.