impls/lib/reducers.mal

   1 ;; Left and right folds.
   2
   3 ;; Left fold (f (.. (f (f init x1) x2) ..) xn)
   4 (def! reduce
   5   (fn* (f init xs)
   6     ;; f      : Accumulator Element -> Accumulator
   7     ;; init   : Accumulator
   8     ;; xs     : sequence of Elements x1 x2 .. xn
   9     ;; return : Accumulator
  10     (if (empty? xs)
  11       init
  12       (reduce f (f init (first xs)) (rest xs)))))
  13
  14 ;; Right fold (f x1 (f x2 (.. (f xn init)) ..))
  15 ;; The natural implementation for `foldr` is not tail-recursive, and
  16 ;; the one based on `reduce` constructs many intermediate functions, so we
  17 ;; rely on efficient `nth` and `count`.
  18 (def! foldr
  19
  20   (let* [
  21     rec (fn* [f xs acc index]
  22       (if (< index 0)
  23         acc
  24         (rec f xs (f (nth xs index) acc) (- index 1))))
  25     ]
  26
  27     (fn* [f init xs]
  28       ;; f      : Element Accumulator -> Accumulator
  29       ;; init   : Accumulator
  30       ;; xs     : sequence of Elements x1 x2 .. xn
  31       ;; return : Accumulator
  32       (rec f xs init (- (count xs) 1)))))