Sat Feb 18 10:28:05 EST 2012

State Space Models: Arrow and generalized functors.

I'm trying to find a good way to represent state-space models in the
standard Haskell type classes (categories?).

The basic form is the relationship between an update equation and
(infinite) sequences.

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

This is a generalization of a haskell Functor in terms of Arrows
instead of functions.

The update equation is an Arrow:

      U s i o   = (s,i) -> (s, o)

Normal Haskell Functor F:

      fmap :: (i -> o) -> (F i -> F o)

Generalized Haskell Functor in terms of arrow A instead of
arrow/function (->):

      fmap' :: A i o -> A (F' i) (F' o)

What I'm interested in is then the less general F' = []

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

Where A = U s is the Arrow parameterized in the threaded state object.

So the final types are something like this:

      fmap  :: Functor f           => (i -> o) -> f i  ->  f o
      gfmap :: Arrow a, GFunctor f => a i o    -> a (f i) (f o)

What is GFunctor?  It's a pattern I don't recognize.  It pops up in
less general form (GFunctor == []) in iterated functions:

      gfmap :: ((s,i) -> (s, o)) -> (s,[i]) -> (s,[o])
      gfmap f (s,[]) = (s,[])
      gfmap f (s, i:is) = (s'', o:os) where
         (s',o)   = f (s,i)
         (s'',os) = gfmap f (s', is)

See next post.

[1] http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Applicative.html#t:WrappedArrow