Hillis beta reduction in Clojure

Danny Hillis’ seminal work The Connection Machine introduced, among many other things, the concept of “beta reduction” on vectors¹ (I dub this “Hillis beta reduction” so as not to confuse the term with traditional beta reduction in the lambda calculus). I found this particular idea fascinating and still applicable today, if only as a quick thought experiment.

Hillis asserted that the everyday fold / reduce routines that we have all come to know and love are merely a subset of a larger scheme of operations that can be performed on ordered data structures. The overarching process is named the “beta function,” and accepts one function and two vectors as arguments. The result of this function is the combination of the two vectors into a map, using the first vector to form the map’s values and the second vector to form the map’s keys. When duplicate keys are found, the provided function is used to “combine” the corresponding values. It’s an interesting process that’s much easier to understand given an example:

(beta + '(1 2 5) '(X Z Z))  ; => {X 1, Z 7}

Using the positions of each element to match keys and values of the map to be formed, the beta function pulls together data like a zip function. When the duplicate key Z is encountered twice, the two values are combined using the + function we provided, and the final value corresponding to the key Z in the map is (+ 2 5), or 7.

What is traditional list folding, then? Why, it’s just beta reduction with a certain constant second argument:

(beta + '(1 2 5) (repeat 1))  ; => {1 8}

When we provide the beta function with the same key for every value (1, in this case), all values are combined to the same key using the provided function. This is reduction in a different form!²

Below is an implementation of Hillis’ beta function in Clojure. I included a shorthand form of the function in which a two-argument call will give the same result as a call to reduce:

(beta + '(1 2 5))  ; => 8

Feel free to play around!

(defn beta
  ([f c1]
     (get (beta f c1 (repeat 1)) 1))
  ([f c1 c2]
     (loop [acc {}
            e1 (first c1) c1 (rest c1)
            e2 (first c2) c2 (rest c2)]
       (if (or (nil? e1) (nil? e2))
         acc
         (let [new-val (if (contains? acc e2)
                         (f (get acc e2) e1)
                         e1)]
           (recur (assoc acc e2 new-val)
                  (first c1) (rest c1)
                  (first c2) (rest c2)))))))