Thu Aug 25 14:30:05 CEST 2011
Streams and the Reader Monad
I'm having trouble following the different ways of formulating
(input-dependent) streams. Oleg wrote down the following bind
function and also mentioned this. See also thread.
data Kl i o = forall s. Kl s (i -> s -> (s, o))
instance Monad (Kl i) where
return x = Kl () (\_ s -> (s,x))
(Kl s m) >>= f = Kl s (\i s -> case f (snd (m i s)) of
Kl s' m' -> (s,snd (m' i s')))
This is different from what I've been trying to accomplish. But let's
try to follow the diagonal bind described here.
In  the join operation for streams is written as producing a stream
from the diagonal of the stream of streams input.
So what is going on here?
Let's just try an example. Let's try to bind the sequence [0,1,2,..]
to i -> [0,i,2*i, ..] according to the definition
0.  0 0 0 ..
1. 0  2 3 ..
2. 0 2  6 ..
3. 0 3 6  ..
.. .. .. .. .. ..
( This cannot represent streams with the kind of iterated (s,i)->(s,o)
dependence I'm looking for. This is really an i -> Stream dependence,
where i determines the whole stream. The trouble is that all rows are
independent of each other: there can be no history relation between
elements of the output stream, only *inside* a single row. )
So what is this stream combination useful for? Let's dig further.
As Oleg mentions in , it's the Reader Monad. Very curious. See
also first comment in . Why? Because streams can be represented
as Nat -> a and the bind would then have type:
(>>=) :: (Nat -> a) -> (a -> Nat -> b) -> (Nat -> b)
a >>= f = \n -> f (a n) n
The reader's bind is a function that takes the environment n and uses
it to evaluate the computation a, using its result to obtain another
computation through f, which will be passed the environment n again.
Defining the stream monad on explicit streams seems confusing.
Formulating it as the Reader monad makes it simpler; te body of the
bind function then looks quite straighforward.
So let's try to put the graph above in this formula:
a n = n -- 0, 1, 2, ..
f i n = n * i -- 0, i, 2i, ..
b n = f (a n) n = n * n
So it's clear, this cannot represent the discrete integral (partial
sum) operation, because b_n is independent of a_m, m != n, and for the
integral it would be dependent on a_m, for m <= n.