Трансдьюсеры

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

См. также вводную статью в блоге, это видео и этот раздел FAQ о хороших случаях использования трансдьюсеров.

Терминология

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

;; reducing function signature
whatever, input -> whatever

Трансдьюсер (иногда называемый xform или xf) - это преобразование от одной редуцирующей функции к другой:

;; transducer signature
(whatever, input -> whatever) -> (whatever, input -> whatever)

Опредение трансдьюсеров и трансформаций

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

Например:

(filter odd?) ;; returns a transducer that filters odd
(map inc)     ;; returns a mapping transducer for incrementing
(take 5)      ;; returns a transducer that will take the first 5 values

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

(def xf
  (comp
    (filter odd?)
    (map inc)
    (take 5)))

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

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

(->> coll
     (filter odd?)
     (map inc)
     (take 5))

Следующие функции создают трансдьюсер, когда входная коллекция опущена: map cat mapcat filter remove take take-while take-nth drop drop-while replace.

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

Трансдьюсеры можно использовать во многих контекстах (о том, как создавать новые, см. ниже).

transduce

Одним из наиболее распространенных способов применения трансдьюсеров является функция transduce, которая является аналогом стандартной функции reduce:

(transduce xform f coll)
(transduce xform f init coll)

transduce немедленно (не лениво) сократит coll с помощью трансдьюсера xform, примененного к сокращающей функции f, используя init в качестве начального значения, если оно предоставлено, или (f) в противном случае. f предоставляет знания о том, как накапливать результат, что происходит в (потенциально stateful) контексте сокращения.

(def xf (comp (filter odd?) (map inc)))
(transduce xf + (range 5))
;; => 6
(transduce xf + 100 (range 5))
;; => 106

Составленный трансдьюсер xf будет вызываться слева направо с последним вызовом редукционной функции f. В последнем примере входные значения будут отфильтрованы, затем увеличены и, наконец, суммированы.

Eduction

Чтобы отразить процесс применения трансдьюсера к coll, используйте функцию eduction. Она принимает любое количество xforms и конечный coll и возвращает сводимое/итерабельное применение трансдьюсера к элементам в coll. Эти применения будут выполняться каждый раз при вызове reduce/iterator.

(def iter (eduction xf (range 5)))
(reduce + 0 iter)
;; => 6

into

Чтобы применить трансдьюсер к входной коллекции и построить новую выходную коллекцию, используйте into (который эффективно использует reduce и переходные процессы, если это возможно):

(into [] xf (range 1000))

Последовательность

Чтобы создать последовательность из применения трансдьюсера к входной коллекции, используйте sequence:

(sequence xf (range 1000))

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

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

Трансдьюсеры имеют следующую форму:

(fn [rf]
  (fn ([] ...)
      ([result] ...)
      ([result input] ...)))

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

Внутренняя функция имеет 3 последовательности, используемые для различных целей:

Примером использования Completion является partition-all, которая должна перебрать все оставшиеся элементы в конце ввода. Функция completing может быть использована для преобразования редуцирующей функции в преобразующую, добавляя стандартную последовательность завершения.

Раннее завершение

В Clojure есть механизм для указания досрочного завершения редукции:

Процесс, использующий Трансдьюсеры, должен проверять и останавливаться, когда шаговая функция возвращает уменьшенное значение. Кроме того, шаговая функция трансдьюсера, использующая вложенные reduce, должна проверять и передавать уменьшенные значения, когда они встречаются. (В качестве примера см. реализацию cat).

Трансдьюсеры с состоянием редукции

Некоторые Трансдьюсеры (такие как take, partition-all и т.д.) требуют состояния в процессе редукции. Это состояние создается каждый раз, когда преобразуемый процесс применяет трансдьюсер. Например, рассмотрим трансдьюсер dedupe, который сводит серию дублирующихся значений в одно значение. Этот трансдьюсер должен помнить предыдущее значение, чтобы определить, следует ли передавать текущее значение:

(defn dedupe []
  (fn [xf]
    (let [prev (volatile! ::none)])
      (fn
        ([] (xf))
        ([result] (xf result))
        ([result input])
          (let [prior @prev]
            (vreset! prev input)
              (if (= prior input)
                result
                (xf result input))))))

В dedupe prev - это контейнер с состоянием, который хранит предыдущее значение во время редукции. Для повышения производительности значение prev является переменным, но может быть и атомом. Значение prev не инициализируется до начала процесса преобразования (например, при вызове transduce). Таким образом, взаимодействия с состоянием содержатся в контексте преобразуемого процесса.

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

Создание трансдуцируемых процессов

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

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

Документация