Mon Feb 18 16:40:15 CET 2013

Lifting primitives

Fold reduces rank, e.g. acumulation of vector -> scalar or for the
sake of argument, from list [t] to scalar t.

The main problem here is typing.

The language does not use explicit array indexing or any other kind of
data structure deconstruction.  In a sense, the containers are always
hidden, and it is assumed every container has a fold combinator, and
all operations can be lifted over all containers (Functors).

In a traditional functional language, a fold over [t] would use a type
(t, t) -> t as accumulator, or t -> t -> t in curried form.

Here we take the inside-out approach of lifting all operations from t
to [t] which means that the accumulation operation also has type [t]
-> [t] -> [t].  In essence: the accumulation combines two sequences to
a new sequence.  One of the input sequences is the sequence we're
accumulating, the other input is a shifted version of the output.

Using the lifted approach, the accumulation ends up with a value of
[t], being the stream of all intermediatly accumulated values, of
which we only need the last element.  Picking that last element is an
operation of type [t] -> t.  Practically, this translates to a a
simple assignment operation since of course we did not keep track of
the accumulator sequence.  However, the key part is that this
assignment can be typed differently on both sides, conceptually
performing the "pick last element" operation.

So it looks like this [t] -> t is at least meaningful and actually
corresponds to a physical operation.