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

Что такое трансдьюсеры?

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

Мы задаём отдельные шаги, например, применить к каждому элементу какую-либо функцию, оставить только элементы, удовлетворяющие предикату, отбросить пять первых элементов и т.п., а затем собираем эти шаги в единый трансдьюсер. При помощи стандартных функций map, filter и т.п. можно создавать трансдьюсеры, задающие отдельные шаги. Далее трансдьюсеры можно соединять с другими трансдьюсерами, применять их к каким-либо коллекциям и получать новые (при помощи функций into и sequence), применять их к коллекциям и выполнять свёртку по результату (при помощи transduce и eduction) и т.п.

Простой пример

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

Например, на входе

(def input
  [[1 2 3 4 5 7]
   [1 0 2 4 5 6]
   [3 0 1 3]])

нужно выдать

[7 6 3]

Для начала выполним первую половину задачи: выберем элементы, стоящие на чётных позициях:

(def only-evens
  (comp (map-indexed vector)
        (filter #(odd? (first %)))
        (map #(nth % 1))))

Мы создали трансдьюсер, который на каждом входном элементе выполняет следующие действия:

1. Запускает vector с текущим индексом и элементом в качестве параметров.
2. Оставляет только те вектора, где на первой позиции стоит нечётное число (т.е. пары «индекс-элемент» из элементов на чётных позициях, индексация в Clojure происходит с нуля).
3. Выбирает из каждого вектора второй элемент.

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

(into [] only-evens [1 2 3 4 5 7])
;; => [2 4 7]

Работает!

При этом, в отличие от такого кода:

(->> [1 2 3 4 5 7]
     (map-indexed vector)
     (filter #(odd? (first %)))
     (map #(nth % 1)))

который на самом деле преобразуется в

(map-indexed vector
             (filter #(odd? (first %))
                     (map #(nth % 1)
                          [1 2 3 4 5 7])))

проход по исходному вектору производится только один раз, промежуточных коллекций не строится (точнее, отличие будет заметно, если во втором случае коллекции не будут ленивыми; вдаваться в эти детали можно было бы, но мне лениво).

Для полноты картины укажу ещё значения, которые появлялись бы на промежуточных шагах вычисления:

(comp (map-indexed vector)       ;; [[0 1] [1 2] [2 3]
                                 ;;  [3 4] [4 5] [5 7]]
      (filter #(odd? (first %))) ;; [[1 2] [3 4] [5 7]]
      (map #(nth % 1))))         ;; [2 4 7]

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

(def xf
  (map #(transduce only-evens max 0 %)))

Запускаем:

(into [] xf input)
;; => [7 6 3]

Всё хорошо! Давайте всё и везде писать на трансдьюсерах!

Некоторые проблемы с трансдьюсерами

Рассмотрим более сложную задачу. Пусть теперь наша последовательность — это некоторые изменения состояния, представляющего собой отображение целых чисел в натуральные. Так, в каждом элементе будет чётное количество чисел, в каждой паре первое число — ключ, а второе — значение, ассоциированное с этим ключом (либо нуль, если значение удалено). Нам нужно на каждый входной элемент выдать отображение с ключом diff и исходными значениями и с ключом img и состоянием.

Например, на входе

(def input
  [[1 2 3 4 5 7]
   [1 0 2 4 5 6]
   [3 0 1 3]])

нужно выдать

[; на первом шаге добавились ключи 1 3 5
 {:diff [1 2 3 4 5 7], :img {1 2, 3 4, 5 7}]
 ; удалили ключ 1, добавили 2, поменяли значение в 5
 {:diff [1 0 2 4 5 6], :img {2 4, 3 4, 5 6}]
 ; удалили ключ 3, добавили 1
 {:diff [3 0 1 3]    , :img {1 3, 2 4, 5 6}]] 

Попытка решения

Попробуем для начала построить вторую часть, значения в img.

(def to-state1
  (comp (map #(apply hash-map %))
        (reduce my-merge {})))

Запускаем:

(into [] to-state1 input)
; NullPointerException   clojure.core/comp/fn--4727 (core.clj:2460)

Упс! Попробуем стандартный вариант без трансдьюсеров, но с двумя проходами:

(->> input
     (map #(apply hash-map %))
     (reduce my-merge {}))
;; => {1 3, 5 6, 2 4}

Всё работает. Почему же с трансдьюсерами вылетает NPE?

Почему возникла проблема?

Быстрое (и неправильное) решение

Правильное решение

Трансдьюсеры в Haskell (или их отсутствие)

Композиция функций

Кондуиты

Сравнение производительности

Мансур Зиятдинов

27 декабря 2016