[<<][compsci][>>][..]

Fri Aug 26 13:02:04 CEST 2011

Are recursive signal processors applicative?

They are arrows[1].  They do not seem to be monads due to structural
limitations; monads allow data-dependent computation structure while
recursive signal processors have a fixed structure[2].  However, they
seem to be a generalization of monads that supports do notation when
the type of the computation is properly fixed.

Formulated as

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

they also do not seem to be applicative due to a data dependency
problem.  It is possible to write an Applicative instance for the
above type, but it is not powerful enough to encode something
isomorphic to (s,i) -> (s,o)

  instance Functor Signal => Applicative Signal where
    pure  v = Signal () $ \_ -> ((), v)
    (<*>) (Signal sf f) (Signal sa a) = Signal (sf, sa) (signalApp f a)

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

  signalApp fi ai = bi where
    bi (s1, s2) = ((s1', s2'), b) where
      (s1', f)  = fi s1
      (s2', a)  = ai s2
      b = f a

The type of Signal (i -> o) is isomorphic to:

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

The state :: s cannot be influenced by the input :: i.
The type signature forbids any connection.

To give a more intuitive explanation of why this is impossible, think
about what happens when the recursion is unfolded.  The resulting type
is [i->o].  Can the functions in that list still depend on each other?

The answer is a clear no.  Those functions have to be pure.  Suppose
the list is [f0,f1,..].  If f1 depended on the input of f0 it would
not be possible to evaluate f1 without evaluating f0 first.  If they
are in a list there is no reason why we could not just ignore f0.

Funny how I still don't trust type signatures ;)
Side channels are always visible!


[1] entry://../meta/20110816-153448
[2] entry://20110821-094135

[Reply][About]

[<<][compsci][>>][..]