Wed Feb 24 22:04:00 CET 2010

Applicative functors

So is a state space update function :: (s,i)->(s,o) an applicative

I wonder.. If this[1] (and the discussion about applicative functors
vs. comonads) contains a solution to the problem of how to represent
streams such that C dataflow loops can be easily extracted.  In any
case, it's probably essential to fully undersetand McBride &
Paterson's applicative functor paper[2].

What about this: the effect is the threading of the state so it is
hidden.  The `pure' part is the conversion of input into output.  The
desired computation is, given a list of inputs (and a state), produce
a list of outputs:

  s -> [i] -> [o]

Now, what if the behaviour itself changes. i.e.:

  [(s,i)->(s,o)] -> [i] -> [o]

Hmm.. What I'm looking for is really a curried state monad.  The
important part is not (s,i)->(s,o) but i->s->(s,o), where s->(s,o) is
a standard (State o) monad.

For example:

> import Control.Monad.State
> import Control.Applicative

> f :: Int -> State Int Int
> f i = do 
>   s <- get
>   put (i + s)
>   return (s + 100)

Now it's possible to map this function over a list of inputs to obtain
a list of stateful computations, which can be chained together using
sequence and instantiated using runState.

> out = runState (sequence $ fmap f [1..10]) 0

I think I'm getting the hang of this.

[1] http://lambda-the-ultimate.org/node/988
[2] http://www.cs.nott.ac.uk/~ctm/IdiomLite.pdf