Home > clojure > Briefly, the “arity-reduce” pattern in Clojure

Briefly, the “arity-reduce” pattern in Clojure

August 20th, 2011 Leave a comment Go to comments

Update: As noted on Reddit, this pattern, as usual, is both old and well-known: induction or structural induction. Duh. :)

Update2:: Or catemorphism perhaps (see comments).

I think it’s a good policy to read as much source code as I write. Writing code will make you better, and you’ll even stumble across some genuinely good approaches to software. However, it’s hard to compete with closely studying other people’s code. With that in mind, I’ve been learning Clojure since late last year and making a point to read the source code for the standard library regularly. It’s really great code and I guess it’s idiomatic Clojure pretty much by definition (with the exception of some of the core preamble).

While exploring Clojure, there’s a pattern that I’ve encountered which I’ll call the “arity-reduce” pattern. If it has an official name, I’m not aware of it. In any case, I’ve seen it many times, but never seen it called out in books or blogs. It came up again today in a 4clojure problem so I figured I’d write it down.

To motivate things, let’s image we’re implementing clojure.core/max, which takes one or more numeric arguments and returns their maximum value. Here’s how I might have approached it when I started learning Clojure:

(defn my-max [x & more] 
  (if more 
    (let [y (first more)] 
      (recur (if (> x y) x y) (next more))) 

This works, but the meaning of the what we’re trying to accomplish is lost in the details of the implementation. Here’s the official implementation:

(defn max
  "Returns the greatest of the nums."
  {:added "1.0"}
  ([x] x)
  ([x y] (if (> x y) x y))
  ([x y & more]
   (reduce max (max x y) more)))

Note how nice and declarative this is. It basically describes the solution to the problem:

  • Given a single argument, return it
  • Given two arguments, return the greater
  • Given more arguments, take the max of the first two args, rinse and repeat.

Maybe I’m slow, but for me, this was an eye-opener. With Clojure I’ve had to learn that whenever I write an anonymous function for use in map or reduce, I should ponder whether a built-in function that does what I need already exists (this is especially true with using sets, maps, and keywords as functions). Similarly, I should always ask my self if multiple arities of the same function would be clearer than jamming the whole implementation into one.

Here are some places where this pattern is used in Clojure:

And a few more that are made clearer by multi-arity definitions although they don’t explicitly use reduce in the “more” case:

  • <, >, and the rest of the comparison functions
  • and
  • or
  • The .., ->, and ->> threading macros

Cheers and happy Clojuring!

Categories: clojure Tags:
  1. Bruce
    August 21st, 2011 at 01:37 | #1

    One of the reasons for the function signatures not containing & more is that it is much faster operating on a known number of parameters than it is applying, reducing or recuring over a list. Lots of stuff in clojure core is like this.

  2. Ed
    August 21st, 2011 at 04:10 | #2

    You should read Richard Bird’s book on haskell. It provides lots of these insights in the first few chapters.

  3. JD
    August 21st, 2011 at 08:04 | #3
  4. August 21st, 2011 at 08:32 | #4

    Thanks! Noted. Although in these cases it seems like the catamorphism and the algebra have been conflated. The catamorphism isn’t a reusable piece of code defined on a datatype.

  1. July 5th, 2012 at 09:38 | #1