What effects are modeled by the stream (infinite list) monad?

Question

Various instances of monads model different type of effects: for example, Maybe models partiality, List non-determinism, Reader read-only state. I would like to know if there is such an intuitive explanation for the monad instance of the stream data type (or infinite list or co-list), data Stream a = Cons a (Stream a) (see below its monad instance definition). I've stumbled upon the stream monad on a few different occasions and I would like to understand better its uses.

data Stream a = Cons a (Stream a)

instance Functor Stream where
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Applicative Stream where
    pure a                      = Cons a (pure a)
    (Cons f fs) <*> (Cons a as) = Cons (f a) (fs <*> as)

instance Monad Stream where
    xs >>= f = diag (fmap f xs)

diag :: Stream (Stream a) -> Stream a
diag (Cons xs xss) = Cons (hd xs) (diag (fmap tl xss))
    where
        hd (Cons a _ ) = a
        tl (Cons _ as) = as

P.S.: I'm not sure if I'm very precise in my language (especially when using the word "effect"), so feel free to correct me.

Byers

It models infinite computations in which you can observe individual steps of the computation. – Mauldon

Answer 1

The Stream monad is isomorphic to Reader Natural (Natural: natural numbers), meaning that there is a bijection between Stream and Reader Natural which preserves their monadic structure.

Intuitively

Both Stream a and Reader Natural a (Natural -> a) can be seen as representing infinite collections of a indexed by integers.

fStream = Cons a0 (Cons a1 (Cons a2 ...))

fReader = \i -> case i of
  0 -> a0
  1 -> a1
  2 -> a2
  ...

Their Applicative and Monad instances both compose elements index-wise. It's easier to show the intuition for Applicative. Below, we show a stream A of a0, a1, ..., and B of b0, b1, ..., and their composition AB = liftA2 (+) A B, and an equivalent presentation of functions.

fStreamA  = Cons  a0     (Cons  a1     ...)
fStreamB  = Cons     b0  (Cons     b1  ...)
fStreamAB = Cons (a0+b0) (Cons (a1+b1) ...)
fStreamAB = liftA2 (+) fStreamA fStreamB

-- lambda case "\case" is sugar for "\x -> case x of"
fReaderA = \case 0 -> a0    ; 1 -> a1    ; ...
fReaderB = \case 0 ->    b0 ; 1 -> b1    ; ...
fReaderC = \case 0 -> a0+b0 ; 1 -> a1+b1 ; ...
fReaderC = liftA2 (+) fReaderA fReaderB = \i -> fReaderA i + fReaderB i

Formally

The bijection:

import Numeric.Natural  -- in the base library

-- It could also be Integer, there is a bijection Integer <-> Natural
type ReaderN a = Natural -> a

tailReader :: ReaderN a -> ReaderN a
tailReader r = \i -> r (i+1)

toStream :: ReaderN a -> Stream a
toStream r = Cons (r 0) (toStream (tailReader r))

fromStream :: Stream a -> ReaderN a
fromStream (Cons a s) = \i -> case i of
  0 -> a
  i -> fromStream s (i-1)

toStream and fromStream are bijections, meaning that they satisfy these equations:

toStream (fromStream s) = s :: Stream a
fromStream (toStream r) = r :: ReaderN a

"Isomorphism" is a general notion; two things being isomorphic usually means that there is a bijection satisfying certain equations, which depend on the structure or interface being considered. In this case, we are talking about the structure of monads, and we say that two monads are isomorphic if there is a bijection which satisfies these equations:

toStream (return a) = return a
toStream (u >>= k) = toStream u >>= (toStream . k)

The idea is that we get the same result whether we apply the functions return and (>>=) "before or after" the bijection. (The similar equations using fromStream can then be derived from these two equations and the other two above).

Sutherlan

Can you elaborate a bit? It's hard for me to understand how exactly do you see ask' :: a defined here. – Haddock

The Reader is another name for the type of functions (I should have said that from the start): type Reader r a = r -> a. I added an explanation of what it means for these types to be isomorphic. – Sutherlan

Answer 2

@Li-yao Xia's answer pretty much covers it, but if it helps your intuition, think of the Stream monad as modeling an infinite sequence of parallel computations. A Stream value itself is an (infinite) sequence of values, and I can use the Functor instance to apply the same function in parallel to all values in the sequence; the Applicative instance to apply a sequence of given functions to a sequence of values, pointwise with each function applied to the corresponding value; and the Monad instance to apply a computation to each value in the sequence with a result that can depend on both the value and its position within the sequence.

As an example of some typical operations, here are some sample sequences plus a Show-instance

instance (Show a) => Show (Stream a) where
  show = show . take 10 . toList
nat = go 1 where go x = Cons x (go (x+1))
odds = go 1 where go x = Cons x (go (x+2))

giving:

> odds
[1,3,5,7,9,11,13,15,17,19]
> -- apply same function to all values
> let evens = fmap (1+) odds
> evens
[2,4,6,8,10,12,14,16,18,20]
> -- pointwise application of functions to values
> (+) <$> odds <*> evens
[3,7,11,15,19,23,27,31,35,39]
> -- computation that depends on value and structure (position)
> odds >>= \val -> fmap (\pos -> (pos,val)) nat
[(1,1),(2,3),(3,5),(4,7),(5,9),(6,11),(7,13),(8,15),(9,17),(10,19)]
> 

The difference between the Applicative and Monadic computations here is similar to other monads: the applicative operations have a static structure, in the sense that each result in a <*> b depends only on the values of the corresponding elements in a and b independent of how they fit in to the larger structure (i.e., their positions in the sequence); in contrast, the monadic operations can have a structure that depends on the underlying values, so that in the expression as >>= f, for a given value a in as, the corresponding result can depend both on the specific value a and structurally on its position within the sequence (since this will determine which element of the sequence f a will provide the result).

It turns out that in this case the apparent additional generality of monadic computations doesn't translate into any actual additional generality, as you can see by the fact that the last example above is equivalent to the purely applicative operation:

(,) <$> nat <*> odds

More generally, given a monadic action f :: a -> Stream b, it will always be possible to write it as:

f a = Cons (f1 a) (Cons (f2 a) ...))

for appropriately defined f1 :: a -> b, f2 :: a -> b, etc., after which we'll be able to express the monadic action as an application action:

as >>= f = (Cons f1 (Cons f2 ...)) <*> as

Contrast this with what happens in the List monad: Given f :: a -> List b, if we could write:

f a = [f1 a, f2 a, ..., fn a]

(meaning in particular that the number of elements in the result would be determined by f alone, regardless of the value of a), then we'd have the same situation:

as >>= f = as <**> [f1,...,fn]

and every monadic list operation would be a fundamentally applicative operation.

So, the fact that not all finite lists are the same length makes the List monad more powerful than its applicative, but because all (infinite) sequences are the same length, the Stream monad adds nothing over the applicative instance.

Vasos

I've found your observation that the Monad and Applicative instances of the Stream are similar in power very enlightening. Thank you! – Neibart

re your "the Applicative instance appl[ies] a sequence of given functions [emphasis mine] to a sequence of values", but what about xs = liftA2 (+) (Cons 0 (Cons 1 xs)) (Cons 1 xs)? there's no (fully) given functions there, i.e. though Applicative it is an essentially sequential computation. maybe what's a "fully given function" can be debated but the essentially sequential nature of that computation I think is totally self-evident. (see this for the background). could you clarify? – Dugong