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

в 14:00, , рубрики: clojure, clojurescript, FRP, functional programming, javascript, transducer, transducers, Программирование, реактивное программирование, функциональное программирование

В первой части мы остановились на следующей спецификации: Трансдьюсер — это функция принимающая функцию step, и возвращающая новую функцию step.

step⁰ → step¹

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

result⁰, item → result¹

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

function flatten() {
  return function(step) {
    return function(result, item) {
      for (var i = 0; i < item.length; i++) {
        result = step(result, item[i]);
      }
      return result;
    }
  }
}

var flattenT = flatten();

_.reduce([[1, 2], [], [3]], flattenT(append), []); // => [1, 2, 3]

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

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

Итак, сейчас мы можем:

  1. Изменять элементы (прим. map)
  2. Пропускать элементы (прим. filter)
  3. Выдавать для одного элемента несколько новых (прим. flatten)

Преждевременное завершение

Но что, если мы хотим прервать весь процесс посередине? Т.е. реализовать take, например. Для этого Рич предлагает заворачивать возвращаемое значение в специальную обертку «reduced».

function Reduced(wrapped) {
  this._wrapped = wrapped;
}
Reduced.prototype.unwrap = function() {
  return this._wrapped;
}
Reduced.isReduced = function(obj) {
  return (obj instanceof Reduced);
}

function take(n) {
  return function(step) {
    var count = 0;
    return function(result, item) {
      if (count++ < n) {
        return step(result, item);
      } else {
        return new Reduced(result);
      }
    }
  }
}

var first5T = take(5);

Если мы хотим завершить процесс, то, вместо того чтобы вернуть очередной result как обычно, возвращаем result, завернутый в Reduced. Сразу обновим сигнатуру функции step:

result⁰, item → result¹ | reduced(result¹)

Но функция _.reduce уже не сможет обрабатывать такую версию трансдьюсеров. Придется написать новую.

function reduce(coll, fn, seed) {
  var result = seed;
  for (var i = 0; i < coll.length; i++) {
    result = fn(result, coll[i]);
    if (Reduced.isReduced(result)) {
      return result.unwrap();
    }
  }
  return result;
}

Теперь можно применить трансдьюсер first5T.

reduce([1, 2, 3, 4, 5, 6, 7], first5T(append), []);    // => [1, 2, 3, 4, 5]

Еще придется добавлять проверку Reduced.isReduced(result) в трансдьюсеры, которые несколько раз вызывают step (прим. flatten). Т.е. если во flatten при очердном вызове step нам вернут результат завернутый в Reduced, мы обязаны завершить свой цикл, и вернуть этот завернутый результат.

Состояние

Еще одна важная деталь, трансдьюсер take имеет состояние. Он запоминает сколько элементов уже через него прошло. Чтобы всё работало правильно, этот счетчик нужно создавать исменно в том месте, где он создан в примере (см. var count), т.е. внутри функции, которая возвращает step. Если бы это была, например, глобальная переменная, то мы бы считали элементы для всех трансьдьюсеров типа take в одном счетчике, и получали бы неправильный результат.

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

function transduce(transducer, append, seed, coll) {
  var initialisedTransducer = transducer(append); // В момент вызова этой функции создаются состояния.
                                                  // initialisedTransducer содержит в себе счетчик,
                                                  // и его (initialisedTransducer) следует использовать только в рамках
                                                  // этого цикла обработки коллекции, после чего уничтожить.
  return reduce(coll, initialisedTransducer, seed);
}

transduce(first5T, append, [], [1, 2, 3, 4, 5, 6, 7]);    // => [1, 2, 3, 4, 5]

Завершение

Мы уже говорили о преждевременном завершении, но может быть и обычное завершение, когда просто кончается исходная коллекция. Некоторые трансдьюсеры могут как-то обрабатывать завершение.

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

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

В clojure эти две функции объединяются в одну, мы в JavaScript тоже можем так сделать.

function step(result, item) {
  if (arguments.length === 2) { // обычный вызов
    // возвращаем step(result, item) или что вам нужно
  }
  if (arguments.length === 1) { // завершительный вызов
    // Здесь необходимо вызвать step c одним аргументом, чтобы передать завершающий сигнал дальше.
    // Но если мы хотим что-то добавить в коллекцию в конце,
    // то мы должны сначала вызвать step с двумя аргументами, а потом с одним.

    // ничего не добавляем
    return step(result);

    // что-то добавляем
    result = step(result, что-то);
    return step(result);
  }
}

Обновим сигнатуру функции step, теперь у нее два варианта в зависимости от числа аргументов:

result⁰ → result¹ *
result⁰, item → result¹ | reduced(result¹)

* я не уверен может ли здесь возвращаться reduced(result¹), из выступления Рича это не ясно. Будем пока считать что не может.

Все трансдьюсеры должны поддерживать обе операции — обычный шаг и завершительный вызов. Также функции transduce() и append() придется обновить, добавив поддержку завершительного вызова.

function transduce(transducer, append, seed, coll) {
  var initialisedTransducer = transducer(append);
  var result = reduce(coll, initialisedTransducer, seed);
  return initialisedTransducer(result);
}

function append(result, item) {
  if (arguments.length === 2) {
    return result.concat([item]);
  }
  if (arguments.length === 1) {
    return result;
  }
}

Итак, вот реализация partition (разбивает коллекцию на маленькие коллекции):

function partition(n) {
  if (n < 1) {
    throw new Error('n должен быть не меньше 1');
  }
  return function(step) {
    var cur = [];
    return function(result, item) {
      if (arguments.length === 2) {
        cur.push(item);
        if (cur.length === n) {
          result = step(result, cur);
          cur = [];
          return result;
        } else {
          return result;
        }
      }
      if (arguments.length === 1) {
        if (cur.length > 0) {
          result = step(result, cur);
          return step(result);
        }
      }
    }
  }
}

var by3ItemsT = partition(3);

transduce(by3ItemsT, append, [], [1,2,3,4,5,6,7,8]);   // => [[1,2,3], [4,5,6], [7,8]]

Инициализация

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

Для этого нужно добавить еще один вариант функции step — вообще без параметров. Если step вызывается без параметров, она должна вернуть начальное значение, например пустой массив.

Очевидно трансдьюсеры не могут создавать пустой массив, так как они не привязаны к обрабатываемому типу коллеции. Но кроме функции step в трансдьюсерах, есть еще внешняя функция step, которая, как раз, знает про тип коллекции. В наших примерах это функция append.

Обновим сигнатуру функции step.

→ result
result⁰ → result¹
result⁰, item → result¹ | reduced(result¹)

Обновим функции transduce() и append()

function transduce(transducer, append, coll) {
  var initialisedTransducer = transducer(append);
  var seed = initialisedTransducer();
  var result = reduce(coll, initialisedTransducer, seed);
  return initialisedTransducer(result);
}

function append(result, item) {
  if (arguments.length === 2) {
    return result.concat([item]);
  }
  if (arguments.length === 1) {
    return result;
  }
  if (arguments.length === 0) {
    return [];
  }
}

И перепишем для примера генератор трансдьюсеров map.

function map(fn) {
  return function(step) {
    return function(result, item) {
      if (arguments.length === 2) {
        return step(result, fn(item));
      }
      if (arguments.length === 1) {
        return step(result);
      }
      if (arguments.length === 0) {
        return step();
      }
    }
  }
}

Получается мы просто перенесли пустой массив из параметра transduce() внутрь append(), на первый взгляд это ненужное действие, но это дало нам возможность создавать трансдьюсеры, которые добавляют что-то в начало коллекции (как те что добавляют в конец, только наоборот).

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

Итоги

На этом всё. Я пересказал весь доклад Рича Хикки. И, как я понимаю, это пока вообще всё что можно рассказать про трансдьюсеры.

Подытожим еще раз что мы получили. Мы получили универсальный способ создавать операции над коллекциями. Эти операции могут: изменять элементы (map), пропускать элементы (filter), размножать элементы (flatten), иметь стейт (take, partition), преждевременно завершать обработку (take), добавлять что-то в конце (partition) и добавлять что-то вначале. Все эти операции мы можем легко объединять с помощью compose, и использовать как на обычных коллекциях, так, например, и в FRP. Кроме того, это всё будет работать быстро и потреблять мало памяти, т.к. не создается временных коллекций.

Это всё круто! Но как нам начать их использовать? Проблема в том, что чтобы использовать трансдьюсеры по максимуму, JavaScript сообщество должно договориться о спецификации (а мы это умеем, да? :-). Тогда мог бы реализоваться крутой сценарий, при котором библиотеки для работы с коллекциями (underscore и пр.) будут уметь создавать трансдьюсеры, а другие билиотеки, которые не совсем про коллекции (напр. FRP), будут просто поддерживать трансдьюсеры.

Спецификация которую предлагает Рич, на первый взгляд, неплохо ложится на JavaScript, за исключением детали про Reduced. Дело в том, что в Clojure уже есть глобальный Reduced (он там уже давно), а в JavaScript нет. Его, конечно, легко создать, но каждая библиотека, будет создавать свой Reduced. В итоге если я, например, захочу добавить поддержку трансдьюсеров в Kefir.js, мне придется добавлять поддержку трансдьюсеров-underscore, трансдьюсеров-LoDash и т.д. Reduced — это слабое место спецификации предлагаемой Ричем.

Другой сценарий — появление разных библиотек про трансдьюсеры, у каждой из которых будет своя спецификация. Тогда мы сможем получить только часть преимуществ. Уже есть библиотека transducers.js, в ней конечно создан свой Reduced, и пока нет поддержки завершительного и начального вызовов, и неизвестно в каком виде автор их добавит.

Ну и учитывая то, что многим трансдьюсеры не кажутся чем-то новым и сильно полезным, пока неясно как мы будем, и будем ли использовать их в JavaScript.

Автор: Pozadi

Источник

Поделиться

* - обязательные к заполнению поля