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:
| Count | Operation |
|---|---|
| 11 | sum
|
| 11 | #(...) (op or abbreviated λ)
|
| 5 | format (I/O is everywhere)
|
| 4 | fn (λ)
|
| 4 | count
|
| 3 | map
|
| 3 | reduce (counting the two to implement sum)
|
| 2 | filter
|
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.)
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