В последнее время определенную известность получили — новая фишка из еще не вышедшей Clojure 1.7. На момент написания статьи актуальна Сlojure 1.7-alpha5, но уже успело появиться изрядное количество портов трансдьюсеров на разнообразные языки:,. И это, по правде говоря, немного обескураживает. Ведь довольно давно (еще в Clojure 1.5) добавили библиотеку.

Так вот про редьюсеры никто особо не говорил, никуда ничего не портировал, хотя, вроде как, делают они схожие вещи Или нет? Давайте разберемся, для чего нам в Clojure понадобились все эти reducers & transducers (они нам правда нужны?), как они работают, как их использовать И выясним наконец, не пора ли выкидывать reducers на свалку.

Будет неправильным описывать концепции, возникшие в Clojure, вне контекста данного языка. Потому дальше будет много листингов на Clojure.

Но зато не будет никакого матана. В общем начальные знания Clojure уместны (особенно представление о ), а вот знать Haskell не обязательно. Также заранее предупреждаю, что все приведенные листинги стандартных функций на самом деле очень сильно изменены, иногда даже «слегка» поломаны.

Все во благо упрощения. Ах да, на картинке тот самый.

Nov 23, 2017 - Файл формата pdf; размером 15,68 МБ. Smart Transducers (Sensors or Actuators), Interfaces, and Networks (Kang Lee).

Сворачиваемся Итак, Clojure язык функциональный, а значит не есть хорошо. Ну и ладно, не очень нам хотелось — есть же функциональноугодный! (defn my-reduce (rf coll;; этот вариант для удобства (if-let s (seq coll) (my-reduce rf (first s) (next s)) (rf))) (rf acc coll (if-let x & xs (seq coll) (recur rf (rf acc x) xs) acc))) В действительности reduce, конечно же, реализован, но нам это сейчас не важно, забудем.

Функция rf (назовем ее редукт-функция) тут принимает два аргумента: первый — некое «скользящее состояние»; второй — элемент из последовательности coll. Если начальное состояние не задано, то используется (first coll) или (rf). Пробегаемся по всей коллекции coll, для каждого элемента вызываем rf, при этом «протаскивая» состояние acc. Когда элементы закончились, то просто возвращаем acc. Небольшой пример.

Допустим, у нас есть список строк, хотим подсчитать их суммарную длину. Вот императивный код с циклом: (defn length-of-strings strings (with-local-vars acc 0;; да-да, в Clojure есть локальные переменные! (doseq c strings (var-set acc (+ @acc (count c))));; собственно вся работа @acc)) Состояние цикла — простой счетчик acc (число).

На каждой итерации мы полагаем его равным (+ @acc (count c)). А теперь еще разок, только через reduce: (defn length-of-strings coll (my-reduce (fn (acc c (+ acc (count c))));; наша редукт-функция 0;; начальное значение coll)) В случае, если временно «подзабыть» о ленивости, то можно многие примитивные операции реализовать, вроде map или filter. (defn my-map f coll (my-reduce (fn acc c (conj acc (f c))) coll)) (defn my-filter p coll (my-reduce (fn acc c (if (p c) (conj acc c) acc)) coll)) Для реализации take приведенный вариант reduce уже не сгодится — цикл всегда пробегает по всей последовательности (это не какой то там Haskell, где все ленивое).

Дабы побороть сей недостаток, в версию 1.5 добавили специальный костыль маркер и соответствующий ему предикат reduced? Заодно переписали reduce, получив что-то наподобие этого: (defn my-reduce (rf coll (if-let s (seq coll) (my-reduce rf (first s) (next s)) (rf))) (rf acc coll (if-let x & xs (seq coll) (let ret (rf acc x) (if (reduced? Ret) @ret (recur rf ret xs))) acc))) Как только редукт-функция вернет нам (reduced.), цикл обрывается и возвращается значение @ret. (defn take-r n coll (my-reduce (fn n1 acc c (if (pos? N1) (dec n1) (conj acc c) (reduced acc))) n coll));; функция поддерживает бесконечные последовательности! (take-r 5 (range));; = 0 1 2 3 4 Нельзя не вспомнить про замечательнейшую функцию. По сути своей это аналог reduce, только возвращает ленивый список из всех промежуточных значений acc, а не только последнее.

Ее весьма удобно использовать при отладке. Пишем шаг алгоритма в виде функции, запускаем reduce на коллекции с входными данными. Если вдруг что-то не так, заменяем reduce на reductions, запускаем в REPL и получаем все промежуточные шаги. С циклами так просто не получится — надо будет городить отладочные костыли, что не очень удобно. Бывает reductions полезна и сама по себе, факториалы там какие посчитать:;; =.ленивая. последовательность факториалов (def factorials (reductions.' (cons 1 (map inc (range))))) (nth factorials 20);; = 176640000 Clojure использует для прохода по коллекциям.

Если мы решим пробежаться по вектору, хеш-таблице или простому итератору, то в куче будет создано изрядное количество временных объектов. Очевидная оптимизация, которая просится в такой ситуации — реализовать специализированный вариант reduce для тех коллекций, для которых это имеет смысл. Ну а если уж коллекция не поддается такой оптимизации, тогда использовать стандартную реализацию, сходную с той, что приведена в начале статьи. Для этого имеется специальный протокол. Когда объект-коллекция его поддерживает, то эта реализация и будет использоваться внутри clojure.core/reduce. Поэтому reduce в Clojure обычно быстрее аналогичного цикла doseq. Трансформеры Трансформер — это такая функция, которая принимает одну редукт-функцию и возвращает новую.

Например, вот трансформер «увеличить на 1»: (defn inc-t rf (fn acc c (rf acc (inc c))));; и сразу пример использования (reduce + 0 (map inc 1 2 3 4));; = 14 (reduce (inc-t +) 0 1 2 3 4);; = 14 Можно это дело несколько обобщить, разрешив вместо inc указывать любую функцию: (defn map-t f (fn rf (fn acc c (rf acc (f c))))) (def inc-t (map-t inc)) (def dec-t (map-t dec));. (reduce (inc-t +) 0 1 2 3 4);; = 14 А вот, например, трансформер «фильтратор»: (defn filter-t pred (fn rf (fn acc c (if (pred c) (rf acc c) acc)))) (def odd?-t (filter-t odd?)) (def even?-t (filter-t even?));; пример (reduce (even?-t.) 1 1 2 3 4);; = 8 А можно ли совместить несколько трансформеров?

(defn odd?-inc-t rf (odd?-t (inc-t rf)));;.или чуть более канонично (def odd?-inc-t (comp (filter-t odd?) (map-t inc)));; что логически эквивалентно. (def odd?-inc-t (comp (fn rf (fn acc c (if (odd? C) (rf acc c) acc))) (fn rf (fn acc c (rf acc (inc c))))));; что даст эквивалент такой функции (defn odd?-inc-t rf (fn acc c (if (odd? C) (rf acc (inc c)) acc)));; пример использования (reduce.

1 (- 1 2 3 4 5 (map inc) (filter odd?)));; = 15 (reduce (odd?-inc-t.) 1 1 2 3 4 5);; 15 Стоит обратить внимание, что трансформеры идут в «обратном» порядке. Если мы хотим, чтобы элементы коллекции обрабатывались трансформером A до того, как они попадут в B, то склеивать их нужно как (comp A B). А теперь фокус: (def cc (vec (range 1000000))) (time (reduce + 0 (- cc (filter odd?) (map inc))));; 'Elapsed time: 171.390143 msecs';; = 00 (time (reduce ((comp (filter-t odd?) (map-t inc)) +) 0 cc));; 'Elapsed time: 93.246015 msecs';; = 00 Вот как, ощутимый прирост скорости на ровном месте!

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

Но в целом результаты совсем не удивительные. При использовании map и filter создается 2 промежуточных последовательности. Мы пробегаем по исходному вектору, создаем временный список из отфильтрованных значений. Затем пробегаем по этому списку и строим еще один, но с увеличенными элементами. И, наконец, пробегаемся уже по нему, суммируя значения. С другой стороны, вариант с трансформерами не создает никаких временных коллекций.

Вместо этого над исходными элементами сразу же применяется и odd?, и inc. Где мои редьюсеры? И было все хорошо, пока версия 1.5 не привнесла новую стандартную библиотеку clojure.core.reducers. Именно так, придется ее явно импортировать. А еще в ней объявлены свои версии map, filter, take-while, и другие. И, конечно же, они не совместимы с обычными версиями из clojure.core.

Поэтому лучше писать (require 'clojure.core.reducers:as r) вместо простого (use 'clojure.core.reducers). Итак, что же такое редьюсер? Кратко и глупо: редьюсер — это всякий объект, по которому можно редьюситься.

Любая коллекция в терминах clojure.core.reducers — это редьюсер. Хеш-таблица — редьюсер. И java.lang.String редьюсер. Ну и nil, разумеется,. Посмотрим определение: (defn reducer coll xf;; `xf` - это трансформер (reify clojure.core.protocols/CollReduce (coll-reduce this f1 (let f2 (xf f1) (clojure.core.protocols/coll-reduce coll f2 (f2)))) (coll-reduce this f1 init (let f2 (xf f1) (clojure.core.protocols/coll-reduce coll f2 init))))) Тут берется коллекция coll, и возвращается новая, по которой можно запустить reduce, и только это.

Ни добавить элемент, ни удалить, ни даже пройтись по элементам. Зато перед каждым запуском reduce редукт-функция будет пропущена сквозь трансформер xf.

(def nums 1 2 3 4 5) (def nums+1 (reducer nums inc-t)) (reduce + 0 nums);; = 15 (reduce + 0 nums+1);; = 20 Как уже упоминалось, в библиотеке reducers объявлены свои варианты map, filter, take-while и подобные. Все они принимают редьюсер и возвращают новый, к которому «прикреплен» соответствующий трансформер. Так бы могла выглядеть clojure.core.reducers/map (она, конечно же, выглядит совсем ): (def map-r f coll (reducer coll (map-t f))) И теперь несколько примеров как все это добро можно использовать: (require 'clojure.core.reducers:as r) (def nums 1 2 3 4 5 6 7 8) (type (map inc nums));; = clojure.lang.LazySeq (reduce conj (map inc nums));; = 2 3 4 5 6 7 8 9 (type (r/map inc nums));; = clojure.core.reducers$folder$reify1234;; совсем-совсем не sequence (reduce conj (r/map inc nums));; = 2 3 4 5 6 7 8 9;; но все еще умеет редьюситься (reduce conj (r/filter odd? Nums));; = 1 3 5 7 (reduce + 0 (- nums (r/map inc) (r/map inc)));; = 52;; (+ 0 (inc (inc 1)) (inc (inc 2)).) (reduce + 0 (- nums (r/filter odd?) (r/map inc)));; = 20;; (+ 0 (inc 1) (inc 3).) Параллелимся Если честно, то «reducers» зря так назвали. Правильнее было бы «folders».

Ведь помимо протокола CollReduce (который появился задолго до reducers), в библиотеке объявлен другой, более важный, протокол CollFold: (defprotocol CollFold (coll-fold coll n combinef reducef)) В принципе очень похоже, только редукт-функций теперь две, а еще добавился непонятный аргумент n. Идея: по некоторым коллекциям можно пробегаться в несколько потоков. Кратко: разбиваем ее на блоки размером примерно n элементов, каждый кусок сворачиваем при помощи #(reduce reducef (combinef)%), затем список результатов (по одному на блок) сворачиваем еще раз, но уже при помощи #(reduce combinef%). Редьюсер, который умеет сворачивать себя параллельно, называется. Всего 2 стандартных коллекции поддерживает протокол CollFold — вектора и хеш-таблицы. (def v (vec (range 10000000)));; линейно, в 1 поток (time (reduce + v));; 'Elapsed time: 648.897616 msecs';; = 0000;; в несколько потоков (time (r/coll-fold v 512 + +));; 'Elapsed time: 187.414147 msecs';; = 0000 Все стандартные редьюсеры, для которых это имеет смысл, реализуют CollFold.

Это, например, r/map, r/filter, r/mapcat, r/flatten. С другой стороны, r/take, r/take-while, r/drop не поддерживают параллелизацию. Выше приводилась реализация r/map. Вот ее обновленный вариант: (def map-r f coll;; просто заменили `reducer` на `folder` (folder coll (map-t f))) Напрямую использовать coll-fold не нужно — для повседневных нужд имеется обертка. В ней задано значение по умолчанию для n (размер блока) — 512. В общем намек ясен — reducers явно предназначены для больших коллекций (1K элементов).

И еще раз: не используйте coll-fold напрямую, вызывайте fold. Ах, есть же еще. Эдакий ускоренный (за счет многопоточности) вариант #(reduce conj %).

Возвращает эта функция объекты, которые реализуют и Counted, и Sequable, и CollFold. (r/map inc 1 2 3);; = # 2 3 4;; что там со скоростью. (def v (vec (range 1000000))) (time (count (reduce conj (r/map inc v))));; 'Elapsed time: 90.124397 msecs';; = 1000000;; что-то не очень, а если через `foldcat` (time (count (r/foldcat (r/map inc v))));; 'Elapsed time: 25.054988 msecs';; = 1000000 (time (count (r/foldcat (r/map inc (r/foldcat (r/map inc v))))));; 'Elapsed time: 32.054988 msecs';; = 1000000;; результат `foldcat`, кстати, тоже foldable (привет, многопоточность) (satisfies?

R/CollFold (r/foldcat ));; = true На сцену врываются В отличие от редьюсеров, трансдьюсеры уже не отдельная библиотека. Это скорее концепция (читай идея), которая будет интегрирована прямо в модуль clojure.core. Ждем это добро в версии 1.7 (совсем чуть-чуть осталось).

Кратко: трансдьюсеры — это те же трансформеры, только иначе названные. Ну ладно, почти: редукт-функции отныне могут принимать не только 0 и 2 аргумента, а еще и 1.

А трансдьюсер, соответственно, это функция от 0-1-2-арной редукт-функции в 0-1-2-арную новую. (def typical-transducer (fn rf (fn (.);; возвращаем начальный элемент (acc.);; непонятно. (acc c.)));; собственно, тут все самое важное, как и раньше;; новый вариант `map-t`, на 33% лучше старого (defn map-t-improved f (fn rf (fn ( (rf));; пробрасываем дальше (acc (rf acc));; пробрасываем дальше (acc c (rf acc (f c))))));; заменяем `c` на `(f c)` 0-арная редукт-функция как и раньше, может быть вызвана, если нужен начальный элемент. Вариант 2-арный используется для, собственно, самой редукции. А 1-арный вариант вызывается в самом конце всей работы (по завершению reduce).

Он нужен в тех случаях, когда нужно «дописать» новые элементы за последним. Пример: трансдьюсер, пропускающий повторы из коллекции: (defn my-dedupe (fn rf;; острожно, состояние! (let prev (atom::none) (fn;; это наша редукт-функция ( (rf)) (acc (rf acc)) (acc c (let p @prev (reset!

Prev c) (if (= p c) acc (rf acc c)))))))) (def rf ((my-dedupe) +)) (reduce rf 0 1 1, 2 2, 3, 1 1);; = 7 (reduce rf 0 1 1, 2 2, 3, 1 1);; = 6;; упс. `rf` не чистая, нельзя ее использовать 2 раза Тонкий момент — наш трансдьюсер возвращает новую редукт-функцию. Причем эта редукт-функция обладает мутабельным состоянием и умеет делать по сути 3 разных вещи (по 1 на арность). Ну прям объект какой-то. Но при этом сам трансдьюсер состоянием не обладает, он лишь выступает в роли некой фабрики. Как пример использования 1-арного варианта редукт-функции приводят. Упрощенная реализация: (defn partition-all-t n (fn rf (let buffer (java.util.ArrayList.

N);; состояние! (fn ( (rf)) (acc (if (.isEmpty buffer);; если буффер пустой - пробрасываем дальше (rf acc);; иначе. Редьюсеры — это частично примененная foldl, с фиксированным списком и «препроцессором» для редукт функции. Собственно этот «препроцессор» и суть трансдьюсер: type RFn a r = r - a - r type Reducer a = forall r.

RFn a r - r - r type Transducer b a = forall r. RFn a r - RFn b r - трансдьюсер `#(map%)` mapt:: (a - b) - Transducer a b mapt f xf r a = xf r (f a) - аналог `clojure.core.reducers/reducer` reducer:: Transducer a b - a - Reducer b reducer xf ls rf a = foldl (xf rf) a ls - трансдьюсер `(map inc)` mytransducer:: Transducer Int Int mytransducer = mapt (+1) mylist:: Int mylist = 1, 2, 3 myreducer:: Reducer Int myreducer = reducer mytransducer mylist main = print $ myreducer (.) 1. Если я правильно понимаю, идея в том, чтобы сворачивать коллекции проходясь по ним только один раз. Для производительности. Я честно пытался прочитать все примеры, но до конца так и не осилил. Ваш пример на Haskell смотрится немного странно, учитывая, что эту простыню можно заменить на обычное foldl (.) 1 $ map (+1) 1,2,3 Правда ли, что мы хотим добиться чего-то типа foldl (+) 0 $ (map succ).

(filter ( 2)). (map (.3)) $ 1,2,3,4 но в форме foldl ((succ. (. 3)) (+)) 0 1,2,3,4 то есть, чтобы комбинировать некомбинируемые средствами языка «трансдюсеры»?

Если да, то я даже не знаю, это, зато будет намного непонятнее. Кстати, в конкретном случае с map-t можно комбинировать с помощью function composition — точки. Правда, с предикатамы filter-t так не сработает, но они комбинируются как моноиды или с помощью list comprehension. Filter (getAll.

FoldMap (All.) odd, (7), ( 7, x. В целом идея понята верно, но упущен один очень важный момент. Мы хотим сворачивать коллекции в Clojure, проходя по ним только один раз. Я привел код на Haskell дабы продемонстрировать что такое трансдьюсеры/редьюсеры с точки зрения типов, как бы мы, если бы вдруг нам приспичило, их могли написать. Посмотрите еще раз на эту «простыню», там даже список как отдельная 0-арная функция объявлен. Это же лишь пример. Вы очень хорошую ссылку привели — в Haskell для производительности добавли.

Так вот трансдьюсеры для Clojure — это тоже своего рода оптимизация. Только ее нельзя спрятать под капотом — язык сильно другой.

Transducer interfacing handbook / Справочник по интерфейсам преобразователей Год выпуска: 1980 Автор: Daniel H. Sheingold / Даниел Х.

Шейнголд Издательство: Analog Devices ISBN: 0-91-6550-05-2 Формат: PDF Качество: Отсканированные страницы Количество страниц: 250 Язык: Английский Описание: Классическая книга о том, как грамотно работать с различными датчиками. Рассмотрены принципы действия различных активных и пассивных датчиков, приведено множество практических схем реализации аналогового интерфейса сопряжения датчиков в различных промышленных и измерительных системах. Подробно рассмотрены теоретические и практические аспекты подавления помех в аналоговых узлах.

Анализированы источники систематических погрешностей и способы линеаризации нелинейных датчиков. Книга предназначена для разработчиков измерительных и промышленных систем.