Iteration classes

The relation between iterates is an equivalence relation. The equivalence classes of this relation are called iteration classes. Non-iterable functions, involutions, and reductions all have a single distinct iteration element so their iteration classes are trivial.

Cycles can be reduced to iterations of an element whose first two elements are minimal. On the other hand, finite automorphisms that have different orders are iterates of one another if the element with the larger order can be iterated by its own order divided by the order of the other element to get the other element.

Iteration properties

Every monoid element has two sets associated with it that define the properties of its iteration:

• Iteration set: this define the set of numbers with which this function can be iterated over. Injective functions include -1 as in their iteration set.
• Iteration equivalence relation: this defines equivalent iteration numbers, for example, all iterations other then zero are equal to one with idempotent elements.

These sets can be described as a single partition of the real numbers that includes a specially flagged set of invalid values. The iteration properties of an element form a distributive lattice, and the meet operation in this lattice describes the iteration properties of the composition of several elements.

Default values of data types

Given default values for record data types like cons cells, then each place in the cons cell is optional, for example:

{} ;-> '(nil)
{first 10} ;-> (10)
{rest '(1 2)} ;-> (nil 1 2)

The constructor for the data type can be implemented by modifying places of the original cons cell. Consider colors as another example, we could declare that the default color value will be black. Now colors can be constructed using RGB or HSL:

{saturation 1, luminosity 0.5} ; red 
{blue 255} ; blue 

Another advantage of having default values for a data type, is that reducing any place becomes as simple as setting the value of that place to its corresponding default value, so for example, a butrest function could set the rest of a cons cell to the empty list. If a data type forms a lattice, the default value could just be the bottom element (e.g zero in positive total orders).

Shape dependent paralellism

Map, reverse, and transpose are paralell operations whose targeting scheme is dependent upon the shape of their argument. For example, here is the targeting scheme generated by the map operation on a list whose shape (or size) is 3 with respect to func:

{(nth 0) func
 (nth 1) func
 (nth 2) func}

On the other hand, reverse operation runs swap operations in parallel. With respect to a list of size five, the reverse operation runs two shape operations leaving the middle unchanged

{(list-places (nth 0) (nth 4)) swap
 (list-places (nth 1) (nth 3)) swap}

Here is the transpose operation on a matrix that is shaped like [[0 1 2] [3 4 5]]:

{(list-places (nth 1) (nth 3) (nth 4) (nth 2)) (shift 4)
 (list-places (compose first dimensions) 
              (compose second dimensions)) swap}}

The transpose operation is much more complicated then the others because it also reverses the dimensions of the grid.

Association structures

A variety of data structures can be described as associations of values to places:

• Records: have a finite collection of places. For example, colors have :red, :green, and :blue places.
• Lists: have an infinite and enumerated set of places. The places in lists and vectors are enumerated by the nth function.
• Hashes: may have anything, even other hashes, as places.

Lists and hashes can both be generalized to container types because unlike records they contain an infinite number of places.

Partitions in lattice theory

Sets are 0-partitions, using the lattice of sets under union and intersection, we can further create a lattice of 1-partitions, a lattice of 2-partitions, and so on.

The lattice of multisets

The join operation in the multiset lattice is provided by taking the maximum value of each key present in any of the multisets and the meet operation is provided by taking the corresponding minimum value.

(defn join-multisets-by
 [func]
 
 (fn 
  ([] {})
  ([a] a)
  ([a b]
    (apply merge
      (map
        (fn [key]
          (func 
            (if (contains? a key) (get a key) 0)
            (if (contains? b key) (get b key) 0)))
        (clojure.set/union (keys a) (keys b))))
  ([a b & more] (reduce func (func a b) more))))
  
(def join-multisets 
  (join-multisets-by max))
  
(def meet-multisets 
  (join-multisets-by min))

Sets can be defined as a particular type of multisets whose values are all equal to one, as such the set lattice is a sublattice of the multiset lattice dealing with just sets. On the other hand, multisets can be represented as sets by replacing the value for each key with an interval set from the minimal value to that number. All distributive lattices can be represented in terms of the multiset lattice.