• Функциональное программирование
• JavaScript

Трансдьюсеры были анонсированы еще в далеком 2014, с тех пор по ним было написано немалое количество статей (раз, два), но ни после одной статьи я не мог сказать, что понимаю трансдьюсеры кристально ясно. После каждый статьи у меня возникало ощущение, что я приблизительно понимаю что-то сложное, но оно все равно оставалось сложным. А потом однажды в голове что-то щелкнуло: "Я ведь уже видел этот паттерн, только он назывался иначе!"

Задача:

Есть массив scores, содержащий результаты проведенных мною игр в футбол в виде объекта с полями:

• gameID — номер игры;
• my — количество очков у меня;
• others — количество очков у моего противника.

Необходимо найти номера первых двух выигранных мною игр.

Исходные данные для задачи (ответ для таких данных — [1, 3]):

const scores = [
  { gameID: 0, my: 1, others: 2 },
  { gameID: 1, my: 2, others: 1 },
  { gameID: 2, my: 0, others: 3 },
  { gameID: 3, my: 3, others: 2 },
  { gameID: 4, my: 3, others: 1 },
  { gameID: 5, my: 0, others: 0 },
  { gameID: 6, my: 4, others: 1 },  
]

Решение №1. Императивный цикл

Давайте начнем издалека, вернемся в те далекие дни, когда мы писали обычные императивные циклы и мучились изменяемым состоянием (соглашусь, что в данном примере это не вызывает каких-либо проблем):

const result = []

// Пробегаемся по всем играм, пока количество результатов не достигнет двух.
for (let i = 0; i < scores.length && result.length < 2; i++) {
  const { gameID, my, others } = scores[i]

  if (my > others) {
    result.push(gameID)
  }
}

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

Решение №2. Array#map и Array#filter

Это уже решение иммутабельное, более выразительное, "современное".

const result =
  scores
    .filter(({ my, others }) => my > others) // выбираем выигрышные
    .map(({ gameID }) => gameID)             // получаем их номер
    .slice(0, 2)                             // берем первые два

Именно так решило бы большинство js-разработчиков в наши дни, полагаю. Но у этого решения есть одна важная проблема: если в предыдущем решении мы делали всего один проход, да и тот не до конца, то сейчас у нас уже аж два полных прохода. Если бы у нас scores содержал миллион элементов, то предикат в filter вызывался бы миллион раз, функция в map применилась бы меньшее, но все равно большое число раз, а в конце мы все равно берем всего лишь два первых элемента. Конечно, преждевременная оптимизация — зло, но это уже ни в какие ворота.

Решение №3. Свертка

Через свертки можно определить [почти] любую операцию над массивами. В этом решении у нас всего один проход:

const result = scores.reduce((result, { my, others, gameID }) => {
  // Если игра выиграна и количество результатов меньше двух,
  // то добавляем номер в результаты.
  if (my > others && result.length < 2) {
    return result.concat([gameID])
  }

  return result
}, [])

Это чем-то напоминает решение с циклами, но тут мы передаем промежуточное состояние явно и иммутабельно. Но проблема осталась — вместо двух проходов у нас теперь один, но он все равно полный, то есть при миллионе элементов мы пройдемся по всему миллиону, даже если нужное число результатов мы уже получили, ведь у стандартного reduce нет возможности выйти из цикла через break. Давайте тогда напишем свой reduce, из которого можно выйти, если вернуть reduced-значение (идею позаимствовал из clojure).

// Класс-обертка для итогового значения аккумулятора.
class Reduced {
  constructor(value) {
    this.value = value
  }
}

// Небольшой хэлпер, чтобы не писать `new`.
const reduced = value =>
  new Reduced(value)

// Рекурсивная реализация reduce с проверкой аккумулятора на reduced-значение.
const reduce = (reducer, state, array) => {
  // Если аккумулятор - reduced-контейнер со значением,
  // то распаковываем и возвращаем значение, завершая цикл.
  if (state instanceof Reduced) {
    return state.value
  }

  if (array.length === 0) {
    return state
  }

  // Рекурсивно вызовем reduce для хвоста массива,
  // применяя первый элемент к состоянию.
  const [x, ...xs] = array
  return reduce(reducer, reducer(state, x), xs)
}

const result = reduce((result, { my, others, }) => {
  if (my > others) {
    if (result.length < 2) {
      result = result.concat(gameID)
    }

    // Завершаем цикл, если набрано нужно число результатов.
    if (result.length >= 2) {
      result = reduced(result)
    }
  }

  return result
}, [], scores)

Ух, теперь-то у нас все быстро (один проход и ровно до тех пор, пока мы не получим нужное количество элементов), но красиво ли? Я считаю, что код выше — страшный: в нем слишком много кода, который не относится к задаче.

Решение №4. Декомпозиция редьюсера, трансдьюсеры

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

1. filterWins фильтрует игры по статусу, то есть пропускает дальше по цепочке только выигранные игры.
2. mapGameID достает из игры ее номер.
3. firstTwo проверяет количество полученных результатов. Если их меньше двух, то вызывает следующую функцию, получает новые результаты, а потом завершает цикл, если набрано нужное количество.
4. appendToResult добавляет номер игры в массив с результатами и возвращает его.

// next - следующая функция в цепочке
const filterWins = next => (result, score) =>
  // Если игра выигрышная, то передаем ее дальше по цепочке
  score.my > score.others
    ? next(result, score)
    : result

const mapGameID = next => (result, { gameID }) =>
  // Передаем дальше номер игры
  next(result, gameID)

// Эта функция позволяет пропустить через себя ограниченное число элементов.
const firstTwo = next => {
  // Мы используем замыкания для добавления локального состояния к нашим редьюсерам.
  // n - количество элементов, которые нужно пропустить дальше для добавления в
  // массив результатов.
  let n = 2

  return (result, score) => {
    // Если есть свободные места, пропускаем игру дальше и уменьшаем их количество.
    if (n > 0) {
      result = next(result, score)
      n -= 1
    }

    // Если свободных мест нет, завершаем цикл.
    if (n <= 0) {
      result = reduced(result)
    }

    return result
  }
}

const appendToResult = (result, gameID) =>
  result.concat([gameID])

const result = reduce(
  // Последовательно трансформируем редьюсер, применяя наши функции к
  // редьюсеру, создавая тем самым цепочку редьюсеров.
  filterWins(mapGameID(firstTwo(appendToResult))),
  [],
  scores,
)

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

Паттерн вам может показаться знакомым, ведь именно так работают middleware. Это и есть middleware. И это и есть трансдьюсеры, потому что трансдьюсеры это и есть middleware. Трансдьюсер — функция, которая принимает один редьюсер и возвращает новый (с дополнительной логикой перед или после вызова редьюсера).

Те, кто слышит понятие middleware впервые, могут ознакомится с ним тут: express.js, laravel, а так же я пробовал вчера объяснить его своими словами: мой пост

В данном решении у нас три трансдьюсера: filterWins, mapGameID и firstTwo, и мы их по последовательно применяем к редьюсеру appendToResult, создавая все более и более сложный редьюсер.

А теперь давайте унифицируем наши трансдьюсеры:

// pred - предикат - функция, которая принимает значение и возвращает true или false.
// Если предикат возвращает true, то пропускаем значение по цепочке дальше, иначе
// возвращаем неизмененный аккумулятор.
const filter = pred => next => (acc, x) =>
  pred(x) ? next(acc, x) : acc

// mapper - функция, которая преобразует один элемент в другой.
const map = mapper => next => (acc, x) =>
  next(acc, mapper(x))

// Принимает редьюсер и создает новый, который выполнится только n раз.
// После n-ого выполнения цикл завершится.
const take = n => next => (acc, x) => {
  if (n > 0) {
    acc = next(acc, x)
    n -= 1
  }

  if (n <= 0) {
    acc = reduced(acc)
  }

  return acc
}

Заодно переименуем редьюсер:

const append = (xs, x) =>
  xs.concat([x])

А так же добавим хэлпер для композиции функций, чтобы убрать лишние скобки:

const compose = (...fns) => x =>
  fns.reduceRight((x, fn) => fn(x), x)

Добавим хэлпер, который применит транcдьюсер к редьюсеру и вызовет reduce с получившимся редьюсером:

const transduce = (transducer, reducer, init, array) =>
  reduce(transducer(reducer), init, array)

Ну и наконец решим задачу с помощью всех этих функций:

const firstTwoWins = compose(
  filter(({ my, others }) => my > others),
  map(({ gameID }) => gameID),
  take(2),
)

const result = transduce(firstTwoWins, append, [], scores)

Получилось красивое, быстрое, функциональное, иммутабельное, готовое к переиспользованию решение.

Вывод:

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

Писать весь код для работы с трансдьюсерами каждый раз вручную не придется, ведь трансдьюсеры уже давно реализованы во многих библиотеках для обработки данных (например в ramda.js или стандартной библиотеке clojure)

Ramda:

const scores = [
  { gameID: 0, my: 1, others: 2 },
  { gameID: 1, my: 2, others: 1 },
  { gameID: 2, my: 0, others: 3 },
  { gameID: 3, my: 3, others: 2 },
  { gameID: 4, my: 3, others: 1 },
  { gameID: 5, my: 0, others: 0 },
  { gameID: 6, my: 4, others: 1 },  
]

{
  const firstTwoWins = compose(
    filter(({ my, others }) => my > others),
    pluck("gameID"),
    take(2),
  )

  const result = transduce(firstTwoWins, flip(append), [], scores)
}

// Или еще лучше
{
  const firstTwoWins = into([], compose(
    filter(({ my, others }) => my > others),
    pluck("gameID"),
    take(2),
  ))

  const result = firstTwoWins(scores)
}

Clojure:

(def scores [{:game-id 0, :my 1, :others 2}
             {:game-id 1, :my 2, :others 1}
             {:game-id 2, :my 0, :others 3}
             {:game-id 3, :my 3, :others 2}
             {:game-id 4, :my 3, :others 1}
             {:game-id 5, :my 0, :others 0}
             {:game-id 6, :my 4, :others 1}])

(defn win? [{:keys [my others]}]
  (> my others))

(def first-two-wins
  (comp (filter win?)
        (map :game-id)
        (take 2)))

(def result (transduce first-two-wins conj [] scores)) ;; [1 3]