I write a lot of reductions: loops that combine every element from a collection in some way. For example, summing a vector of integers:

(reduce (fn [sum x] (+ sum x)) 0 [1 2 3])
; => 6

If you’re not familiar with Clojure’s reduce, it takes a reducing function f, an initial accumulator init, and a collection xs. It then invokes (f init x0) where x0 is the first element in xs. f returns a new accumulator value acc1, which is then passed to (f acc1 x1) to produce a new accumulator acc2, and so on until every x in xs is folded into the accumulator. That accumulator is the return value of reduce.

In writing reductions, there are some problems that I run into over and over. For example, what if you want to find the mean of some numbers in a single pass? You need two accumulator variables–a sum and a count. The usual answer to this is to make the accumulator a vector tuple. Destructuring bind makes this… not totally awful, but a little awkward:

(reduce (fn [[sum count] x]
          [(+ sum x) (inc count)])
        [0 0]
        [1 2 3 4 5 6 7])
; => [28 7]

Ah, right. We need to divide sum by count to get the actual mean. Fine, we’ll wrap that in a let binding:

(let [[sum count] (reduce (fn [[sum count] x]
                            [(+ sum x) (inc count)])
                          [0 0]
                          [1 2 3 4 5 6 7])]
  (/ sum count))
; => 4

This is awkward for a few reasons. One is that we’ve chewed up a fair bit of indentation, and indentation is a precious commodity if you’re an 80-column masochist like me. Another is that we’ve got the accumulator structure specified in four different places: the let binding’s left hand side, the fn arguments, the fn return value(s), and the initial value. When the reducing function is large and complex, these expressions can drift far apart from one another. They may not even fit on a single screen–start juggling a half-dozen variables and it’s easy for init to get out of sync with the fn args. Not the end of the world, but a little frustrating. Then there’s the runtime overhead. Creating and tearing apart all those vectors comes with significant performance cost.

We could write this as a loop:

(loop [sum   0
       count 0 
       xs    [1 2 3 4 5 6 7]]
  (if (seq xs)
    (recur (+ sum (first xs)) (inc count) (next xs))
    (/ sum count)))
; => 4

No let binding, significantly less indentation. Brings the initial values for accumulators directly next to their names, which is nice. No vector destructuring overhead.

On the flip side, we now burn a lot of time in seq machinery: next allocates a seq wrapper for every single step. Clojure’s reduce traverses the internal structure of vectors without these wrappers, and is significantly more efficient. We also have this extra boilerplate for sequence traversal, and the traversal logic is mixed together with the reduction accumulator. When we used reduce, that traversal was implicit.

Enter Loopr

Check this out:

(require '[dom-top.core :refer [loopr]])
(loopr [sum   0
        count 0]
       [x [1 2 3 4 5 6 7]]
       (recur (+ sum x) (inc count))
       (/ sum count))
; => 4

loopr is a hybrid of loop and reduce. Like loop, it starts with a binding vector of accumulator variables and initial values. Then it takes a binding vector of iteration variables: for each x in the vector [1 2 3 4 5 6 7], it evaluates the third form–the body of the loop. Just like Clojure’s loop, that body should recur with new values for each accumulator. The fourth argument to loopr is a final form, and is evaluated with the final values of the accumulators bound. That’s the return value for the loop.

Like loop, it keeps initial values close to their names, and needs no destructuring of accumulators. Like reduce, it leaves iteration implicit–closer to a for loop. It avoids the need for wrapping the reduce return value in another destructuring let, and requires much less indentation.

Did I mention it’s faster than both the reduce and loop shown here?

(def bigvec   (->> (range 10000) vec))
(def bigarray (->> (range 10000) long-array))
(def bigseq   (->> (range 10000) (map identity)))

(quick-bench   
  (loop [sum   0
         count 0
         xs    bigvec]
    (if-not (seq xs)
      [sum count]
      (let [[x & xs] xs] 
        (recur (+ sum x) (inc count) xs)))))
; Evaluation count : 456 in 6 samples of 76 calls.
;              Execution time mean : 1.366176 ms
;     Execution time std-deviation : 23.450717 µs
;    Execution time lower quantile : 1.334857 ms ( 2.5%)
;    Execution time upper quantile : 1.392398 ms (97.5%)
;                    Overhead used : 20.320257 ns

(quick-bench
  (reduce (fn [[sum count] x]
            [(+ sum x) (inc count)])
          [0 0]
          bigvec))
; Evaluation count : 588 in 6 samples of 98 calls.
;              Execution time mean : 1.284103 ms
;     Execution time std-deviation : 118.742660 µs
;    Execution time lower quantile : 1.106587 ms ( 2.5%)
;    Execution time upper quantile : 1.354247 ms (97.5%)
;                    Overhead used : 20.320257 ns

(quick-bench
  (loopr [sum 0, count 0]
         [x bigvec]
         (recur (+ sum x) (inc count))))
; Evaluation count : 792 in 6 samples of 132 calls.
;              Execution time mean : 793.698823 µs
;     Execution time std-deviation : 52.061355 µs
;    Execution time lower quantile : 763.412280 µs ( 2.5%)
;    Execution time upper quantile : 883.322045 µs (97.5%)
;                    Overhead used : 20.320257 ns

How so fast? loopr macroexpands into loop over a mutable iterator, loop with aget for arrays, or reduce, depending on some heuristics about which tactic is likely to be fastest for your structure. It speeds up multi-accumulator reduce by squirreling away extra accumulators in stateful volatiles.

Multidimensional Reductions

Another problem I hit all the time: reducing over nested collections. Say we’ve got a bunch of people, each one with some pets:

(def people [{:name "zhao"
              :pets ["miette" "biscuit"]}
             {:name "chloe"
              :pets ["arthur meowington the third" "miette"]}])

And I wanted to, say, find the set of all pet names. With nested collections, we need a new reduce for each level of nesting.

(reduce (fn [pet-names person]
          (reduce (fn [pet-names pet]
                    (conj pet-names pet))
                  pet-names
                  (:pets person)))
        #{}
        people)
; => #{"biscuit" "miette" "arthur meowington the third"}

(I know you could write this with a single level of reduce via into or set/union, but we’re using this to illustrate a pattern that’s necessary for more complex reductions, especially those in 3 or 4 dimensions.)

Two problems here. One is that those reduces chew up indentation real quick. Another is that we wind up specifying pet-names over and over again–threading it in and out of the inner reduce. Reduce is kind of backwards too–the things it starts with, the initial value and the collection, come last. The whole thing reads a bit inside-out.

What about loop? Any better?

(loop [pet-names    #{}
       people       people]
  (if-not (seq people)
    pet-names
    (let [[person & people] people
          pet-names (loop [pet-names pet-names
                           pets      (:pets person)]
                      (if-not (seq pets)
                        pet-names
                        (let [pet (first pets)]
                          (recur (conj pet-names pet)
                                 (next pets)))))]
      (recur pet-names people))))
; => #{"biscuit" "miette" "arthur meowington the third"}

Ooof. Again we’re threading accumulators in and out of nested structures, and the loop bodies are interwoven with iteration machinery We could fold this all into a single loop, in theory…

(loop [pet-names    #{}
       people       people
       pets         (:pets (first people))]
  (if-not (seq people)
    pet-names ; Done with outer loop
    (if-not (seq pets)
      ; Done with this person, move on to next
      (recur pet-names (next people) (:pets (first (next people))))
      (let [[pet & pets] pets]
        (recur (conj pet-names pet) people pets)))))

It is shorter, but there are so many ways to get this subtly wrong. I made at least four mistakes writing this loop, and it’s not even that complicated! More complex multi-dimensional iteration is (at least for my brain) playing on nightmare mode.

We do have a lovely, simple macro for nested iteration in Clojure: for.

(for [person people
      pet    (:pets person)]
  pet)
; => ("miette" "biscuit" "arthur meowington the third" "miette")

Problem is for returns a sequence of results, one for each iteration–and there’s no ability to carry accumulators. It’s more like map than reduce. That’s why loopr can take multiple iteration bindings. Just like for it traverses the first binding, then the second, then the third, and so on. Each binding pair has access to the currently bound values of the previous iterators.

(loopr [pet-names #{}]
       [person people
        pet    (:pets person)]
       (recur (conj pet-names pet)))

Without an explicit final expression loopr returns its sole accumulator (or a vector of accumulators, if more than one is given). We get a clear separation of accumulators, iterators, and the loop body. No nesting, much less indentation. It performs identically to the nested reduce, because it actually macroexpands to a very similar nested reduce. Both are about 40% faster than the nested loop with seqs.

Early Return

In reduce we use (reduced x) to return a value immediately; in loop you omit recur. The same works in loopr. Here, we find the first odd number in a collection, returning its index in the collection and the odd value.

(loopr [i 0]
       [x [0 3 4 5]]
       (if (odd? x)
         {:index i, :number x}
         (recur (inc i))))
; => {:index 1, :number 3}

With zero accumulators, loopr still iterates. This can be helpful for side effects or search. Here’s how to find a key in a map by that key’s corresponding value. Note that iterator bindings support the usual destructuring syntax–we can iterate over a map as [key value] pairs.

(loopr []
       [[k v] {:x 1, :y 2}]
       (if (= v 2)
         k
         (recur))
       :not-found)
; => :y

If we don’t return early, loopr returns the final form: :not-found.

Arrays

Sometimes you write an algorithm which reduces over vectors or other collections as a prototype, then start using arrays for speed. loopr can compile the same reduction to a loop using integer indices and aget operations. Just tell it you’d like to iterate :via :array.

(def ary (long-array (range 10000)))
(loopr [sum 0]
       [x ary :via :array]
       (recur (+ sum x)))
; => 49995000

This is on par with (reduce + ary) for single-dimensional reductions. For multi-dimensional arrays loopr is ~65% faster on my machine, though you do have to explicitly type-hint. Faster still with multiple accumulators, of course.

(def matrix (to-array-2d (repeat 1000 (range 1000))))
(loopr [sum 0]
       [row                     matrix :via :array
        x   ^"[Ljava.lang.Long;" row    :via :array]
       (recur (+ sum x)))
; => 499500000

You can control the iteration tactic for each collection separately, by the way. Here’s the average of the numbers in a vector of vectors, where we traverse the outermost vector using a reduce, and the inner vectors using a mutable iterator.

(loopr [count 0
        sum   0]
       [row [[1 2 3] [4 5 6] [7 8 9]] :via :reduce
        x   row                       :via :iterator]
       (recur (inc count) (+ sum x))
       (/ sum count))
; => 5

In Summary

I’m always hesitant to introduce nontrivial macros. That said, in the last five months I’ve written a lot of code with and without loopr, and I’ve found it frequently useful. It’s often clearer and more efficient than the code I was already writing, and it makes refactoring complex reductions less difficult. If you’d like to give it a shot, you’ll find it in dom-top, which is a small control flow library. You’ll find tons of examples and Criterium benchmarks in the test suite. I hope loopr helps you too.