## Tuesday, September 6, 2011

### Antireduce

Antireduce is an useful function in sequence pattern recognition. Antireduce takes a binary operation (usually the inverse of some other binary operation) and returns the result of applying it across a sequence of values:

(defn antireduce
[op coll]

(map
(fn [i]
(if (= i 0)
(first coll)
(op (nth coll i) (nth coll (dec i)))))
(range (count coll))))


For example, we can apply this function to the triangular-numbers:

(= (take 4 (iterate (partial antireduce -)
[0 1 3 6 10 15 21 28 36 45])

(0 1 3 6 10 15 21 28 36 45)
(0 1 2 3 4 5 6 7 8 9)
(0 1 1 1 1 1 1 1 1 1)
(0 1 0 0 0 0 0 0 0 0))


Alternatively, we can use this on the factorial function by using the higher inverse-hyper-operator, division.

(= (take 2 (iterate (partial antireduce /)
[1 1 2 6 24 120 720 5040 40320 362880]))

(1 1 2 6 24 120 720 5040 40320 362880)
(1 1 2 3 4 5 6 7 8 9))


The antireduce function itself can be reversed:

(defn reducify
[op coll]

(map
(fn [i]
(reduce op (map (partial nth coll) (range (inc i)))))
(range (count coll))))


This function should allow us to automatically recognise some basically sequences.