Трансдьюсеры в JavaScript. Часть первая

Рич Хикки, автор языка Clojure, недавно придумал новую концепцию — Трансдьюсеры. Их сразу добавили в Clojure, но сама идея универсальна и может быть воспроизведена в других языках.

Сразу, зачем это нужно:

• трансдьюсеры могут улучшить производительность, т.к. позволят не создавать временные коллекции в цепочках операций map.filter.takeWhile.etc
• могут помочь переиспользовать код
• могут помочь интегрировать библиотеки между собой, например underscore/LoDash могут уметь создавать трансдьюсеры, а FRP библиотеки (RxJS/Bacon.js/Kefir.js) могут уметь их принимать
• могут упростить FRP библиотеки, т.к. можно будет выбросить кучу методов, добавив один метод для поддержки трансдьюсеров

Трансдьюсеры — это попытка переосмыслить операции над коллекциями, такие как map(), filter() и пр., найти в них общую идею, и научиться совмещать вместе несколько операций для дальнейшего переиспользования.



Мы уже умеем совмещать несколько операций:

  function mapFilterTake(coll) {
    return _.take(_.filter(_.map(coll, mapFn), filterFn), 5);
  }

  // (я буду использовать в примерах методы из underscore.js)

Но здесь есть ряд проблем:

• mapFilterTake() может работать только с определенным типом коллекций
• его нельзя использовать в ленивом стиле
• это будет работать медленно с большими коллекциями, ведь на каждом шаге создается временная большая коллекция, и, так как в конце .take(5), бОльшая часть работы вообще будет делаться впустую
• мы не можем ипользовать mapFilterTake() в FRP/CSP библиотеках

Чтобы объяснить идею трансдьюсеров нужно начать с операции reduce. Если подумать, любая операция над коллекциями может быть выражена через reduce. Начнем с операции map.

function append(coll, item) {
  return coll.concat([item]);
}

var newColl = _.reduce(coll, function(result, item) {
  return append(result, mapFn(item));
}, []);

// аналогичный код через map
var newColl = _.map(coll, mapFn);

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

Я добавил еще служебную функцию append(), которая просто оборачивает .concat(), дальше станет понятно зачем это нужно.

Теперь выразим filter через reduce.

var newColl = _.reduce(coll, function(result, item) {
  if (filterFn(item)) {
    return append(result, item);
  } else {
    return result;
  }
}, []);

// аналогичный код через filter
var newColl = _.filter(coll, filterFn);

Надеюсь, что здесь тоже всё понятно.

Дальше следовало бы рассказать про .take(), но с ним всё немного сложнее и я расскажу об этом во второй части статьи, пока разберемся с filter и map.

Давайте теперь внимательно посмотрим на функции которые мы передаем в reduce чтобы имитировать map и filter.

function(result, item) {
  return append(result, mapFn(item));
}

function(result, item) {
  if (filterFn(item)) {
    return append(result, item);
  } else {
    return result;
  }
}

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

function(step) {
  return function(result, item) {
    return step(result, mapFn(item));
  }
}

function(step) {
  return function(result, item) {
    if (filterFn(item)) {
      return step(result, item);
    } else {
      return result;
    }
  }
}

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

Давайте проверим, что пока всё работает.

var mapT = function(step) {
  return function(result, item) {
    return step(result, mapFn(item));
  }
}

var filterT = function(step) {
  return function(result, item) {
    if (filterFn(item)) {
      return step(result, item);
    } else {
      return result;
    }
  }
}

var newColl = _.reduce(coll, mapT(append), []);
var newColl = _.reduce(coll, filterT(append), []);

Вроде работает :-)
Здесь mapT и filterT означает «трандьюсер мап» и «трандьюсер фильтр».

Перед тем как двигаться дальше, давайте еще напишем функции которые генерируют трансдьюсеры разных типов (пока только map и filter).

function map(fn) {
  return function(step) {
    return function(result, item) {
      return step(result, fn(item));
    }
  }
}

function filter(predicate) {
  return function(step) {
    return function(result, item) {
      if (predicate(item)) {
        return step(result, item);
      } else {
        return result;
      }
    }
  }
}

// теперь можно писать так
var addOneT = map(function(x) {return x + 1});
var lessTnan4T = filter(function(x) {return x < 4});

_.reduce([1, 2, 3, 4], addOneT(append), []);      // => [2, 3, 4, 5]
_.reduce([2, 3, 4, 5], lessTnan4T(append), []);   // => [2, 3]

Если посмотреть на параметры функции step(), то можно заметить, что у нее точно такие же типы парметров и возвращаемого значения как и у функций возвращаемых трансдьюсерами (тех что мы передаем в reduce). Это очень важно, потому что это позволяет объединять несколько трансдьюсеров в один!

var addOne_lessTnan4 = function(step) {
  return addOneT(lessTnan4T(step));
}

// или, что вообще замечательно, можно использовать функцию _.compose
var addOne_lessTnan4 = _.compose(addOneT, lessTnan4T);

// и, конечно, можно использовать наш новый трансдьюсер
_.reduce([1, 2, 3, 4], addOne_lessTnan4(append), []);    // => [2, 3]

Итак, мы научились объединять функции для работы с коллекциями новым способом, и назвали объекты, которые мы объединяем и получаем в результате объединения трансдьюсерами. Но удалось ли решить проблемы объявленые вначале статьи?

1) mapFilterTake() может работать только с определенным типом коллекций

Наш трандьюсер addOne_lessTnan4 ничего не знает про тип коллекции, которую мы его заставляем обрабатывать.
Мы можем использовать другой тип данных. Чтобы получить на выходе не массив, а например объект,
достаточно заменить функцию append, и начальное значение [].

_.reduce([1, 2, 3, 4], addOne_lessTnan4(function(result, item) {
  result[item] = true;
  return result;
}), {});    // => {2: true, 3: true}

Чтобы изменить тип входных данных, нужно вместо _.reduce() использовать другую функцию, которая умеет перебирать этот тип. Это тоже не сложно сделать.

2) mapFilterTake() нельзя использовать в ленивом стиле

Так как при обработке коллекции трансдьюсером не создается временных коллекций, а каждый элемент обрабатывается от начала и до конца полностью, мы можем не обрабатывать элементы которые пока не нужны. Т.е. можно написать метод похожий на _.reduce(), который не будет сразу отдавать результат, а позволит вызывать .getNext() для получения следующего обработанного элемента. Или можно организовать ленивость как-нибудь еще.

3) mapFilterTake() будет работать медленно с большими коллекциями

Очевидно у трансдьюсеров здесь всё схвачено.

4) мы не можем ипользовать mapFilterTake() в FRP/CSP библиотеках

Так как трансдьюсеры не привязанны к типу обрабатываемой коллекции, и не создают промежуточных результотов, их можно использовать даже с такими коллекциями как поток событий или Behaviour/Property. Также их можно использовать и в CSP — подходе похожем на FRP. И потенциально можно будет использовать в чем-то новом, чего еще нет.

Во второй части я расскажу как сделать трансдьюсеры take, takeWhile и пр, и о том, что же нам теперь с этим всем делать в JavaScript сообществе.

Трансдьюсеры в JavaScript. Часть вторая

Ссылки по теме:

blog.cognitect.com/blog/2014/8/6/transducers-are-coming — первое упоминание (если не ошибаюсь)
phuu.net/2014/08/31/csp-and-transducers.html — про CSP и трасдьюсеры в JavaScript
jlongster.com/Transducers.js--A-JavaScript-Library-for-Transformation-of-Data — еще раз про трасдьюсеры в JavaScript и немного про CSP
www.youtube.com/watch?v=6mTbuzafcII — Рич Хикки подробно рассказывает про трасдьюсеры