Sunday, March 25, 2012

Simplifying function calls

Argument equivalence:
A function is symmetric if arguments with different orders are all equivalent to one another:
(= (+ 1 2 3)
(apply + #{1 2 3}))

Monoids are variadic functions such that two adjacent constant arguments can be reduced by their application and other calls to the monoid can be reduced in place:
(= (* 1 2 3 (* 4 5) (+ x y))
(* 120 (+ x y)))

Constant reduction and combiner rewriting
After reducing a function's input argument we can reduce the call to the function itself. If the argument given to the function is constant then we can replace the call to the function with its result:
(= (apply + #{1 2 3}) 6)

In certain conditions the call to the function can be replaced with the call to another function:
(= (* 120 (+ x y))
(+ (* 120 x) (* 120 y)))

In this case, we can replace the multiplication operation with an addition operation using the distributive law.

Iteration equvialence:
Each function has an iteration equivalence relation associated with it that represents rather or not the function is equal when iterated to different numbers. This includes the order of the function which states a number which you can mod out of any iteration number without effecting it. Functions that have an order of two are involutions:
(comp reverse reverse)
(comp - -)
(comp / /)
(comp inc dec)

If every value in the iteration equivalence relation is either equal to the identity or one then that function is idempotent:
(= (comp abs abs) abs)
(= (comp int int) int)

In order to use the iteration properties of a function it is important to know when two functions are of the same iteration class.

Reflexivity:
The reflexivity of a function describes an equivalence relation which states that certain parts of a data structure are uneffected by this function. For example, additive negation doesn't effect the absolute value of a number:
(= (comp abs -) abs)

The complemented of the targeted place of the function is included in the reflexivity because it isn't effected by applying the function.