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

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

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

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

https://stackoverflow.com/a/51420884/6440264

По такому выражению, как 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. Чтобы различать функцию сокращения, я рассматриваю некий пользовательский механизм Typing с использованием отражения, но чтобы сосредоточиться на этом вопросе, пока я хотел бы просто применить

    const isReducer = f => (typeof f === 'функция');

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

    const head = (a, b) => a; const хвост = (а, б) => б;

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

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

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


person Community    schedule 19.07.2018    source источник
comment
невозможно указать начальное значение для бинарных операций, таких как head и tail — они в любом случае не являются допустимыми бинарными операциями для reduce, так как их типы не подходят. Пожалуйста, перестаньте злоупотреблять типами функций как структурами данных, и вы поймете, почему.   -  person Bergi    schedule 19.07.2018
comment
Я думаю, вы ошибаетесь, потому что тип предоставляется самой бинарной операцией, а (a,b)=> a или (a,b)=> b ЯВЛЯЕТСЯ бинарной операцией. Если вы не настаиваете, пожалуйста, дайте нам ссылку.   -  person    schedule 19.07.2018
comment
@Bergi Если бинарная операция не является ассоциативной, она недействительна для reduce, но голова и хвост ассоциативны, поэтому они являются допустимыми операторами для reuduce   -  person    schedule 19.07.2018
comment
Я не понимаю, что означают head и tail. Обычно вы связываете их со списками, где они имеют типы list<a> -> a и list<a> -> list<a>, которые вообще не являются бинарными операциями.   -  person Bergi    schedule 19.07.2018
comment
@Bergi Как написано выше: head = (a,b)=> a и tail = (a,b)=> b. По сути это известные бинарные операторы редуктора моноидов. Я дам вам образец в моем ответе здесь.   -  person    schedule 20.07.2018
comment
@KenOKABE Я думаю, ты имеешь в виду head и last. Когда вы сказали tail, это смутило и Берги, и меня, потому что конец списка — это все, кроме первого элемента.   -  person Aadit M Shah    schedule 20.07.2018
comment
@AaditMShah О, да, извините меня за неправильное использование термина. Да, это last.   -  person    schedule 20.07.2018


Ответы (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.

person Aadit M Shah    schedule 19.07.2018
comment
Это отличный пост от вас, как обычно. Однако я полностью впечатлен тем, что не указывать начальное значение - это скорее правильный подход, я считаю, что я не могу согласиться, и чтобы доказать это, я публикую свой ответ. - person ; 20.07.2018