Friday, March 30, 2012

Partitions and unions

A collection can be described as a whole that consists of several parts. Partition functions go from the whole to the parts and union functions go from the parts to the whole. Partitions and unions can be encoded in a single bijection that goes from the whole to the parts and back again. For example, here is a seqify function that goes from a whole object to first and rest parts:
(defn seqify
[coll]

{:first (first coll)
:rest  (rest coll)})

(defn unseqify
[coll]

(vec (cons (:first coll) (:rest coll))))

All one-way functions operate on selected parts of a partition such that the returned whole cannot be reconstructed from the selected parts. For example, you can't reconstruct a list from its first element alone, so the first function is one-way. Monoids are union functions that join together several parts into a new whole and that have a notion of an empty part. Monoids are one-way functions because each object is the product of several different types of partitions.