Stream m a b is a computation in some Monad
m that
delivers a sequence of elements of type
a followed by a
result of type
b.
More concretely, a value of type
Stream m a b can be run
using
runStreamInternal in the Monad
m, and it
delivers either
- the final result: Done b, or
- Yield a str where a is the next element in the
stream, and str is the rest of the stream
- Effect mstr where mstr is some action running in
m which generates the rest of the stream.
Stream is itself a Monad, and provides an operation
yield that
produces a new element of the stream. This makes it convenient to turn
existing monadic computations into streams.
The idea is that Stream is useful for making a monadic computation
that produces values from time to time. This can be used for knitting
together two complex monadic operations, so that the producer does not
have to produce all its values before the consumer starts consuming
them. We make the producer into a Stream, and the consumer pulls on
the stream each time it wants a new value.
Stream is implemented in the "yoneda" style for efficiency. By
representing a stream in this manner
fmap and
>>=
operations are accumulated in the function parameters before being
applied once when the stream is destroyed. In the old implementation
each usage of
mapM and
>>= would traverse the
entire stream in order to apply the substitution at the leaves.
The >>= operation for
Stream was a hot-spot in the ticky
profile for the
ManyConstructors test which called the
cg function many times in
StgToCmm.hs