Sat Mar 13 12:14:53 CET 2010

State breaks composition

More correctly it breaks composition of _function_ and requires the
less powerful composition of _instance_, which is a combination of
function and state (i.e. an object).

In Haskell, stateful computations are modeled as state _transitions_
which keeps the model purely functional.

                           s -> (a,s)

One builds a program as a (large!) state transition built from
primitive state transitions, and then supplies it with an initial
state to set it in motion.  This keeps composition by abstracting out
state completely.

External (physical) state is captured in much the same way by the IO
monad[3], which relates function composition and real-world state.
This synchronizes external at key points with intermediate nodes in
the evaluation of a function network.

             type IO a = RealWorld -> (a, RealWorld)


  * Also in the more theoretical work about complexity theory one uses
    this machine->network transition.  In the first lecture in [2] the
    link is made between turing machines (TM) and combinatorial
    networks (CN) by ``unrolling'' the turing machine in time to yield
    a network.  The main point being that by mechanical translation, a
    polynomial time TM algorithm can be converted into a polynomial
    size CN.  The converse does not seem to be proved, but in practice
    one can usually find a TM for a CN. (``morally equivalent'')

[1] http://en.wikipedia.org/wiki/Flip-flop_(electronics)
[2] http://sms.cam.ac.uk/collection/545358
[3] http://www.haskell.org/haskellwiki/IO_inside