Mon Aug 15 14:47:14 CEST 2011

Applicative approach

It looks like my current abstraction doesn't work well in an
Applicative, Num world.  Let's try to do it differently, working in a
pointwise style.

What I read in [1] -- focusing on a single line in a big article as
sigfpe suggests -- is that some quantification is necessary to put
this into Applicative:

    "Arrow is equivalent to a Category instance, plus a universally
    quantified applicative instance for any fixed domain"

What this means is that you can only combine the outputs.

So let's scrap it and start over: build everything from the start as a
sequence abstraction, where operators are sequences of (time-varying)

ssmApp :: (s1      -> (s1,       (a -> b))) ->  -- fi
          (s2      -> (s2,       a)) ->         -- ai
          (s1, s2) -> ((s1, s2), b)             -- bi
ssmApp fi ai = bi where
  bi (s1, s2) = ((s1',s2'), b) where
    (s1', f)  = fi s1
    (s2', a)  = ai s2
    b = f a

The data type and Applicative instance then become:

data SSM a = forall s. SSM s (s -> (s, a))
instance Functor SSM => Applicative SSM where
  pure  v = SSM () $ \_ -> ((), v)
  (<*>) (SSM sf f) (SSM sa a) = SSM (sf, sa) (ssmApp f a)

That seems straightforward.  Let's go down the path and define the
other operations.

Trouble starts when I'm trying to make a state-dependent i -> o
function.  Why is this?  It seems to be the problem I ran into before

The trouble seems to be in converting (s,i) -> (s,o) into s -> (s,
i->o) because the output state can depend on the input.

Can this be solved by making the type of the composition more general?
I.e. :

signalApp :: (s1      -> (s1,       (s1 -> a -> b))) ->  -- fi
             (s2      -> (s2,       a)) ->               -- ai
             (s1, s2) -> ((s1, s2), b)                   -- bi

Nope.. this messes up the whole Applicative type because it leaks
through.  Maybe the type needs to be:

data Signal a = forall s. Signal s (s -> (s, s -> a))

This still doesn't work because s can depend on i.  Why not write that
explicitly, separating state update and output equation?

fun  s -> i -> s
     s -> i -> o

val  s -> s
     s -> o

Wait.  For something carrying a function, make the state also depend
on the input.

val  s -> s, o
fun  (i -> s) -> (i -> s, i -> o)

Can we make that work?  I'm loosing the point...  It can't be that
hard if it is at all possible.  Dead end.

Backtracking to the previous version, using Applicative it does become
very simple to make Num work:

instance (Eq (Signal a), Num a) => Num (Signal a) where
  (+) = liftA2 (+)
  (*) = liftA2 (*)
  abs = fmap abs
  signum = fmap signum
  fromInteger = pure . fromInteger

So there is definitely some utility in having an Applicative
interface.  The trouble is that I currently can't express this.

To make it more explicit, why can't this work?

currySSM :: ((s,i) -> (s,o)) ->
            (s -> (s, i -> o))
currySSM ssm = f where            
  f s = (s', io) where
    io i = o where
      (s', o) = ssm (s, i)

The trouble here is that s' depends on the input of io.  Is there a
way to re-arrange this such that order of evaluation is enforced,
i.e. that s' is never evaluated before the input is applied to io?

I don't think it's possble to write a function like that, except when
it passes the state without updating.  Let's investigate in another
article how to maybe do this with separate state and output equations.

[1] http://cdsmith.wordpress.com/2011/07/30/arrow-category-applicative-part-i/
[2] entry://20110814-170902