Reducers

Почему linked list это отстой

SPb FProg, 12 Apr 2013, Dmitry Groshev@lambdadmitry

Очень краткое введение в Clojure

Вектор:

[1 2 3]

Применение функции:

(foo a b c)

Определение функции:

(defn foo [x y z] (+ x y z))

Анонимная функция, сахарная версия:

(#(map inc %) [1 2 3])

Очень краткое введение в Clojure

Threading macro:

(-> a (foo b) (bar c d))

(bar (foo a b) c d)

(->> a (foo b) (bar c d))

(bar c d (foo b a))

Foldl(r) considered slightly harmful

Linked list

a = 1:2:3:[]

(cons a (cons b (cons c ())))

• удобная и простая абстракция
• последователен по своей сути
• никакого произвольного доступа, только последовательный
• никакого параллелизма (order promises)

Map

(defn map [f coll]
  (cons (f (first coll)) (map f (rest coll))))

• как? рекурсивно
• как? по порядку
• как? лениво
• из чего? из списка (seq)
• во что? в список (seq)
• очень много смысла

Foldl/foldr

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

• как? рекурсивно
• как? по порядку
• как? лениво
• из чего? из списка (seq)
• во что? в список (seq)
• очень много смысла

sequentiality это тюрьма

много хуже чем мало

Shiny reduce

Reduce

(defn reduce [f init coll]
  (clojure.core.protocols/coll-reduce coll f init))

• безразличен к структуре коллекции
• общий интерфейс для коллекций (reducible) плюс sequential fallback
• строит любую структуру
• не ленив
• имеет порядок вычисления (foldl)
• loops → HOFs on lists → generics → deordering

Секрет успеха

• map over under reduce
• порядок неважен
• deforestation для бедных

(reduce + 0 (map inc [1 2 3])) ; allocates chunks!

S.foldl (+) 0 $ S.map (+1) $ S.stream [1, 2, 3] -- does not

Map-under-reduce

    val
     |
---reduce--
/ | | | | \
| | | | | |
f f f f f f <- map
| | | | | |
a b c d e f

Filter-under-reduce

    val
     |
---reduce--
/ |   |
| |   |
p p p p p p <- filter
| | | | | |
a b c d e f

Reducing functions

(defn mapping [f]
  (fn [f1]
    (fn [result input]
      (f1 result (f input)))))

(defn filtering [pred]
  (fn [f1]
    (fn [result input]
      (if (pred input)
        (f1 result input)
        result))))

(defn mapcatting [f]
  (fn [f1]
    (fn [result input]
      (reduce f1 result (f input)))))

• модификация функции вместо модификации данных
• минимум смысла

Reducer

(defn reduce [f init coll]
  (clojure.core.protocols/coll-reduce coll f init))

(reduce + 0 (map inc [1 2 3]))

VS

(reduce + 0 (reducer [1 2 3] (mapping inc)))

(defn rmap [f coll] (reducer coll (mapping f)))

(reduce + 0 (rmap inc [1 2 3]))

• код выглядит так же
• те же структуры данных
• в Clojure с версии 1.5

Генерализация

• map: fn * seqable → seqable
• rmap: fn * reducible → reducible

Composability

(defcurried map [f coll] (reducer coll (mapping f)))

(def foo (comp (r/filter even?) (r/map inc))) ; currying!
(reduce + (foo [1 1 1 2])) ; 6

||

map/reduce

(reduce + 0 (parallel-map inc (break-into-chunks data)))

filter это проблема (map отображает 1:1, нужен Maybe)

reduce/combine

(combine + 0
  (parallel-map #(reduce + 0 (rmap inc %))
                (break-into-chunks data)))

combine тоже reduce

reduce отображает M:N

fold

(combine-fn + 0
  (parallel-map #(reduce-fn + 0 (rmap inc %))
                (break-into-chunks data)))

(r/fold + + (r/map inc (r/filter even? data)))

• reducer игнорирует порядок (map/filter VS take 5th)
• (combine-fn) возвращает id (reduce seed)
• (combine-fn x id) → x
• (кстати, это моноид)
• seqable fallback
• vector в Clojure это дерево с branching factor 32
• внутри Fork/Join

Профит

(def v (into [] (range 10000000)))               ; 10m elements
(time (reduce + (map inc (filter even? v))))     ; 470-490msec
(time (reduce + (r/map inc (r/filter even? v)))) ; 260-290msec
(time (r/fold + (r/map inc (r/filter even? v)))) ; 150-160msec (2 cores)

Не только факториалы

• Java NIO mmap
• реализует построчный reducible (с простым индексом)
• прекрасно работает с параллельным fold'ом

;; Count number of non-empty fields in TSV file
(->> (iota/vec filename)
     (r/filter identity) ;; filter out empty lines
     (r/map
        #(->> (clojure.string/split % #"[\t]" -1)
              (filter (fn [^String s] (not (.isEmpty s))))
              count))
     (r/fold +))

Не только Clojure

Вопросы?

Ссылки:

• Rich Hickey про reducers (EuroClojure talk)
• Он же, обзорная статья
• Он же, более подробная статья
• Слайды: https://github.com/si14/fprog-2013-04-slides