Thu Oct 13 13:55:44 EDT 2011

Lifting pure functions to dataflow functions

One of the problems that has been puzzling me for a while is to find a
good representation of the transformation that maps a pure
"applicative" function to a dataflow function.

The simplest case is one input, one output:

    (i -> o)   ->   (i' -> o' -> m ())

Here i, o are value types, while i' and o' are reference types, and m
is some kind of monad that keeps track of the reference one-time
binding or multiple assignment.

Generalizing this to multiple in/out is straightforward when the
outputs are encoded in a recursive tuple type as mentioned before.

    (i1 -> i2 -> o1 :& o2)  ->

    (i1' -> i2' -> o1' -> o2' -> m ())

An ad-hoc way would be to implement this for assignable references,
though with some more effort it should be possible to use one-time
binding as in the data flow language in Concepts, Techniques, and
Models of Computer Programming[1].  Here the input and output types
could be constrained by type classes.

I wonder, isn't this just lifting functions to Arrows?

[1] http://www.info.ucl.ac.be/~pvr/book.html