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

Guy Steele at ACM SIGPLAN 2009

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)

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

https://github.com/thebusby/iota
  • 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

Работает в ClojureScript (без параллельного fold'а)

Вопросы?

Ссылки: