Правильно ли я понимаю преобразователи?

Question

Давайте начнем с определения: transducer - это функция, которая принимает reducer функцию и возвращает reducer функцию.

A reducer - это двоичная функция, которая принимает аккумулятор и значение и возвращает аккумулятор. Редуктор может быть выполнен с функцией reduce (примечание: все функции каррированы, но я разобрался с этим, также как и определения для pipe и compose для удобства чтения - вы можете увидеть их в live демо ):

const reduce = (reducer, init, data) => {
  let result = init;
  for (const item of data) {
    result = reducer(result, item);
  }
  return result;
}

С помощью reduce мы можем реализовать функции map и filter:

const mapReducer = xf => (acc, item) => [...acc, xf(item)];
const map = (xf, arr) => reduce(mapReducer(xf), [], arr);

const filterReducer = predicate => (acc, item) => predicate(item) ?
  [...acc, item] :
  acc;
const filter = (predicate, arr) => reduce(filterReducer(predicate), [], arr);

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

const even = n => n % 2 === 0;
const double = n => n * 2;

const doubleEven = pipe(filter(even), map(double));

doubleEven([1,2,3,4,5]);
// first we get [2, 4] from filter
// then final result: [4, 8]

Преобразователи помогают нам решить эту проблему: когда мы используем преобразователь, не создаются временные массивы, и мы можем обобщать наши функции для работы не только с массивами. Для работы преобразователей требуется функция transduce Обычно преобразователи выполняются путем передачи функции transduce:

const transduce = (xform, iterator, init, data) =>
  reduce(xform(iterator), init, data);

const mapping = (xf, reducer) => (acc, item) => reducer(acc, xf(item));

const filtering = (predicate, reducer) => (acc, item) => predicate(item) ?
  reducer(acc, item) :
  acc;

const arrReducer = (acc, item) => [...acc, item];

const transformer = compose(filtering(even), mapping(double));

const performantDoubleEven = transduce(transformer, arrReducer, [])

performantDoubleEven([1, 2, 3, 4, 5]); // -> [4, 8] with no temporary arrays created

Мы даже можем определить массив map и filter, используя transducer, потому что он настолько компонуем:

const map = (xf, data) => transduce(mapping(xf), arrReducer, [], data);

const filter = (predicate, data) => transduce(filtering(predicate), arrReducer, [], data);

живая версия, если вы хотите запустить код -> https://runkit.com/marzelin/transducers

Имеет ли смысл мои рассуждения?

Answer 1

Ваше понимание правильное, но неполное.

В дополнение к описанным вами концепциям преобразователи могут выполнять следующие действия:

• Поддерживать семантику раннего выхода
• Поддержка семантики завершения
• Сохранение состояния
• Поддержка значения инициализации для функции шага.

Так, например, реализация в JavaScript должна будет выполнитьthis:

// Ensure reduce preserves early termination
let called = 0;
let updatesCalled = map(a => { called += 1; return a; });
let hasTwo = reduce(compose(take(2), updatesCalled)(append), [1,2,3]).toString();
console.assert(hasTwo === '1,2', hasTwo);
console.assert(called === 2, called);

Здесь из-за вызова take операция восстановления завершается рано.

Необходимо иметь возможность (опционально) вызывать функцию шага без аргументов для начального значения:

// handles lack of initial value
let mapDouble = map(n => n * 2);
console.assert(reduce(mapDouble(sum), [1,2]) === 6);

Здесь вызов sum без аргументов возвращает аддитивную идентичность(ноль), чтобы заполнить сокращение.

Чтобы выполнить это, вот вспомогательная функция:

const addArities = (defaultValue, reducer) => (...args) => {
  switch (args.length) {
    case 0: return typeof defaultValue === 'function' ? defaultValue() : defaultValue;
    case 1: return args[0];
    default: return reducer(...args);
  }
};

Это принимает начальное значение (или функцию, которая может обеспечить его) иРедуктор для семян для:

const sum = addArities(0, (a, b) => a + b);

Теперь sum имеет правильную семантику, и это также, как определяется append в первом примере.Для преобразователя с отслеживанием состояния посмотрите на take (включая вспомогательные функции):

// Denotes early completion
class _Wrapped {
  constructor (val) { this[DONE] = val }
};

const isReduced = a => a instanceof _Wrapped;
// ensures reduced for bubbling
const reduced = a => a instanceof _Wrapped ? a : new _Wrapped(a);
const unWrap = a => isReduced(a) ? a[DONE] : a;

const enforceArgumentContract = f => (xform, reducer, accum, input, state) => {
  // initialization
  if (!exists(input)) return reducer();
  // Early termination, bubble
  if (isReduced(accum)) return accum;
  return f(xform, reducer, accum, input, state);
};

/*
 * factory
 *
 * Helper for creating transducers.
 *
 * Takes a step process, intial state and returns a function that takes a
 * transforming function which returns a transducer takes a reducing function,
 * optional collection, optional initial value. If collection is not passed
 * returns a modified reducing function, otherwise reduces the collection.
 */
const factory = (process, initState) => xform => (reducer, coll, initValue) => {
  let state = {};
  state.value = typeof initState === 'function' ? initState() : initState;
  let step = enforceArgumentContract(process);
  let trans = (accum, input) => step(xform, reducer, accum, input, state);
  if (coll === undefined) {
    return trans; // return transducer
  } else if (typeof coll[Symbol.iterator] === 'function') {
    return unWrap(reduce(...[trans, coll, initValue].filter(exists))); 
  } else {
    throw NON_ITER;
  }
};

const take = factory((n, reducer, accum, input, state) => {
  if (state.value >= n) {
    return reduced(accum);
  } else {
    state.value += 1;
  }
  return reducer(accum, input);
}, () => 0);

Если вы хотите увидеть все это в действии, я сделал небольшую библиотеку некоторое время назад.Хотя я игнорировал протокол взаимодействия от Cognitect (я просто хотел получить концепции), я попытался реализовать семантику как можно точнее, основываясь на выступлениях Рича Хики из Strange Loop и Conj.