[<<][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][>>][..]