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

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[1].  See also thread[2].

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

In [1] 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  0  ..
  1.  0 [1] 2  3  ..
  2.  0  2 [4] 6  ..
  3.  0  3  6 [9] ..
  .. .. .. .. ..  ..

( 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 [2], it's the Reader Monad.  Very curious.  See
also first comment in [1].  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[1] 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.


[1] http://patternsinfp.wordpress.com/2010/12/31/stream-monad/
[2] http://www.mail-archive.com/haskell-cafe@haskell.org/msg92702.html



[Reply][About]
[<<][compsci][>>][..]