Streams vs monads

Question

Does exist any difference between streams (lazy lists) and monads? From conceptual and mathematical points of view, not from technical implementation. Or else, does exist biunique, one-to-one correspondence between? More exactly, as streams it means "even streams" from the SRFI-41 of the Scheme language. Is it another category than monads? If so, what category is it? May "even streams" guarantee the control of side effects, like monads?

Accepted Answer

As Salil already said, the two are different concepts:

A stream is a (potentially infinite) list of values, typically, but not necessarily, computed in lazy fashion, i.e., only storing some way of computing the values when requested. There's a lot of examples around that do not involve monads in any way:

```
(define integers (cons-stream 1 (stream-map (lambda (x) (+ x 1)) integers))
```

It is quite useful to also consider finite, precomputed, lists as streams, since you can use them anywhere a (potentially or necessarily) finite lazy stream could be used.

So, a stream is something that has an operation `next: streamType -> (valueType streamType)` to get the next value and the remaining stream.

Monads, on the other hand, are less of a data structure and more a way of writing source code by combining individual commands.

Probably the simplest useful example is the “Maybe monad” – I'm not sure what it would look like in Scheme, sorry, but the idea is: Given a list of computations `(f g h)` and an input `x`, carry out the computations in order, almost as if given `(f (g (h x)))`, but let each function fail gracefully: If `g` returns `nil`, do not invoke `(f nil)`, but instead, return `nil` immediately.

You can, of course, combine the two in various useful ways and compute your stream values with monads or encapsulate the use of streams like I/O streams that are not exactly following the expectations of functional programming in a monad (to avoid code storing a reference to some previous state of the stream), but they serve completely different purposes. Think about the abstraction layer (close the cover, don't look at the innards): A monad, applied to functions, gives you a function. A stream, on the other hand, is not some higher function, but a list of values.

Obviously, the function defined by (or returned from, depending on your point of view) the monad can be an implementation of a stream, and also, the values extracted from a stream can be monads. But as you can see above, there are monads implementing things completely different from streams. Whether there are streams not implemented as monads probably depends on just what exactly you use the term for. I must confess I'm not sure at the moment if infinite streams properly qualify as monads; finite lists obviously do.

Streams vs monads

Solution

Problem