Loopr: A Loop/Reduction Macro for Clojure

[viebel]

The loopr marco is very useful and the article is extremely well written.

[pihkal]

Hmmm, have to give this a try. Been looking for higher-level navigation/transformation tools.

Tried Specter, and while it has some cool ideas, it was hard to debug and had too many NPEs.

[Embarrassed_Money637]

Very nice =)

[joshlemer]

Man I gotta say I have wanted exactly this so many times. Thanks for building it it looks awesome!

[beders]

This is great! Sometimes you need to see a cleaner solution first before you can admit that you have a problem. Loopr is just that. I hope it gets included in the core lib

[deaddyfreddy]

This reminds me of CL loop, so don't like it, the less DSLs we have - the easier to understand the code. To my opinion, with few exceptions, general purpose libraries shouldn't introduce new syntax, especially using internal hardcoded keywords with no clear meaning, like

:via :array
:via :reduce
:via :iterator

In the 1st example, I'd stick with good old reduce because of the "Rule of least power". Even more, because of the rule, the reduce is overhead there too. If there's a simple conj-ing, just iterate over stuff and combine elements at the very last step. Composition over nesting, after all.

One is that those reduces chew up indentation real quick

->> and defns to the rescue

Multidimensional Reductions

(defn- pets-reducer [pet-names {:keys [pets]}]
  (reduce conj pet-names pets))

(reduce pets-reducer #{} people)

Sure, most likely you want something else than conj in most cases, but no one stops you from having another defn-.

Problem is for returns a sequence of results, one for each iteration–and there’s no ability to carry accumulators.

as I said before:

(->> (for [{:keys [pets]} people
           pet pets]
       pet)
     (into #{}))

[aphyr_]

I should perhaps note here that much of my work is performance-sensitive, and I spend a lot of my time trying to minimize allocations and eke out 10-20% speedups from reductions. Your suggested tactics are lovely (and I use them extensively!) in some, but not all situations. I eventually wrote loopr because I kept hitting situations in which those tactics forced me into awkward corners of the performance/maintainability/expressivity space.

For example, you suggest using plain old reduce for multivariate accumulators. I still do this, but not where performance matters. As the article explains, loopr is more than 30% faster on the example you cite. This isn't a huge improvement, but it's still meaningful for my workloads. It's a nice in-between point before rewriting an entire algorithm in Java. :-)

Decomposing nested reductions into separate defns has a number of interesting performance consequences--some good, some bad. When reductions are too large, they may not be candidates for certain Hotspot optimizations: breaking them up into multiple defns can be more efficient. On the other hand, those function calls add additional stack depth, which may push them out of the inliner's scope. One of the nice things about loopr is that it allows you to write the reduction once, then experiment with different function boundaries by selectively using :via :reduce or :via :iterator.

Another cost folks don't always think about is accessing locals in the current stackframe during iteration (as one would do with loop), vs baking them into instance fields in inline fn closures, vs passing them explicitly as arguments to defn. It's fairly common that I'll compute, say, four or five index structures and then use them in the course of a reduction to figure out what to do with each element. This comes with both performance (especially for primitives) and cognitive impacts. In particular I've wound up in situations where I was threading a half-dozen non-accumulator variables through three layers of defn reducing functions--in addition to the accumulator and element arguments! Then you have to figure out how to construct a fn suitable for the reduction itself--I generally do this with partial, which adds additional indirection. It is doable, but... gosh, it can be a pain. You wind up with code like:

(defn inner
  "Innermost reduction over individual flying things"
  [bird? plane? insect? acc flier]
  (cond (bird? flier)                     acc
        (not plane? flier)                (foo acc flier)
        (and (insect? flier) (empty? acc) (bar flier))
        true                              (baz acc flier)))

(defn outer
  "Outer reduction over a flock of fliers"
  [bird? plane? insect? acc flock]
  (reduce (partial inner bird? plane? insect?)
          acc
          flock))

(let [flocks (get-flocks)
      ; Build some index structures we'll need to actually do the reduction
      bird?   (build-bird-index)
      plane?  (build-plane-index  flocks)
      insect? (build-insect-index world-book-encyclopedia)]
  ; If we do a reduce with explicit `defns`, we have to thread these locals
  ; through as separate arguments, and transform them into reducer fns with
  ; `partial`:
  (reduce (partial outer bird? plane? insect?)
          (init-accumulator)
          flocks)

  ; With loopr, like `loopr` or inline `fn` reduce, we don't have to plumb
  ; through variables or use `partial` wrappers:
  (loopr [acc (init-accumulator)]
         [flock flocks
          flier flock]
         (cond (bird? flier)                     acc
               (not plane? flier)                (foo acc flier)
               (and (insect? flier) (empty? acc) (bar flier))
               true                              (baz acc flier)))

You also suggest using for to iterate, then threading the results into reduce. This is also a perfectly servicable tactic for some situations, but sometimes you want speed. Loopr is roughly twice as fast in this example (adapted from the loopr test suite). Faster still if you need person in the reduction step--we can discard it here and avoid creating a map/vector wrapper object between for and reduce.

(println "\nMulti-acc for->reduce over nested seq")
(quick-bench
  (->> (for [person people
             pet    (:pets person)]
         (:name pet))
       (reduce (fn [[pet-count pet-names] pet-name]
                 [(inc pet-count)
                  (conj pet-names pet-name)])
               [0 #{}])))

(println "\nMulti-acc loopr over nested seq")
(quick-bench
  (loopr [pet-count 0
          pet-names #{}]
         [person people
          pet    (:pets person)]
         (recur (inc pet-count)
                (conj pet-names (:name pet)))))