Function of the day: sum

Most folds are sums — either (fold + 0 ...) or (fold + 0 (map f ...)). In math and pseudocode, they're written as Σ or sum, not as folds. So programming languages should support writing them the same way. In Clojure:

(defn sum "Add the elements of a collection, or some function of them."
  ([xs] (reduce + xs))
  ([f xs] (reduce (fn [a x] (+ a (f x))) 0 xs)))

This is one of those trivial conveniences that I use with surprising frequency — more than many more familiar operations. Counts from a 286-line Clojure program:

CountOperation
11sum
11#(...) (op or abbreviated λ)
5format (I/O is everywhere)
4fn (λ)
4count
3map
3reduce (counting the two to implement sum)
2filter

sum may be trivial, but at least in this program, it's more common than map, reduce, and filter combined. Isn't that enough to deserve a place in the library?

(For performance reasons, Clojure's + isn't an ordinary generic function and thus can't be taught to work on vectors, so sum doesn't either. This program does vector arithmetic, so I had to duplicate various arithmetic operations for vectors, so three of these uses of sum were actually of a separate vsum. But this distinction would not be necessary in an ideal language.)

1 comment:

  1. Additionally, when + is generic you often don't want to implement sum as a fold! For specific element types there are often much more appropriate ways: For floats you want to keep the cumulative errors down, for things with expensive add operations (e.g. strings if you use + for concatenation, or unions of sets, etc) you might want to do the add in terms of a buffer and convert at the end

    ReplyDelete

It's OK to comment on old posts.