Sun Sep 20 18:51:45 CEST 2009

Combinations of 2D filter masks and mappable scalar ops.

Main rationale: boundary conditions significantly complicate
expression of folds over images.  Write an algebra of fusable
operations, first ignoring boundary conditions (infinite fold), and
second taking that into account.

Parameterizing composition of 2D filter masks will yield a large class
of useful programs, and will probably give some idea about how to move
on to more serious folds.

So... How to express data types?  Or can this be avoided?

Moving to the simpler problem of 1D filter masks over the stream s,
which consists of an infinite list of elements s = e*, this is about
the operator Z wich delays the stream by one time instance.

       Q: what does `Z + 1' mean?

Here Z is an operator: s -> s
this makes 1 also an operator: s -> s
and + is an operator combinator:  (s->s, s->s) -> ((s,s)->s)

It looks like it is actually this shift operator that makes things so
problematic.  The reason is that it ``looks inside'' an iteration over
a stream.

What I mean is that, while it is easy to lift + to a stream operation
(s,s) -> s and feed it with two streams s and Zs, it is less trivial
to turn the operation into an operation f : s->s, where f is obtained
from +,1 and Z.

More specificially, the function that provides arguments from the
input stream to the scalar + : (e,e) -> e somehow needs to retain
memory.  This ``state maintenance'' seems to be the central problem
related to combining maps + folds and stream shift operators.

In other words, there is a difference between the following lift
types, depending on lift over streams, or lift over s,Zs.

   S-lift : ((e,e) -> e)   ->  ((s,s) -> s)

   Z-lift : ((e,e) -> e)   ->  (s -> s)

Making these functions explicit and providing laws for them is
probably what needs to be done.  The lower one can be separated in as

         ((s -> s),
          (s -> s),
          ((e,e) -> e)) -> (s -> s)

i.e. taking two stream transformers and a binary scalar op, and
feeding the transformed streams into the binary element op.  Filling
in 1,Z,+ gives the filter function f mentioned above.

So.. the interaction between

    map2 : ((e,e)->e, s ,s) -> ((s, s) -> s)
    map1 : ((e->e), s) -> (s->s)
    Z    : (s -> s)

    streamZ s = (s -> (s,s))

    map2(+, s, Z(s)) = map1(+,streamZ(s)) : s->s

It's important to distinguish between a stream of tuples and a tuple
of streams.  It looks like making the types work is going to bring us
half way there (in the light of Wadler's free theorems[1]).

[1] http://homepages.inf.ed.ac.uk/wadler/papers/free/free.ps