streams.md

# Stream Fusion

The fused 'Stream' type employs stream fusion for C-like performance when
looping over data. It represents the stream as a state machine using an
explicit state, and a step function working on the state. A typical stream
operation consumes elements from the previous state machine in a stream
pipeline, transforms the elements and yields new values for the next stage to
consume. One stream operation typically represents one stage of a modular
pipeline, representing a single task, stages in the pipeline have no knowledge
of the state of the previous or next stage.

A typical stream pipeline consists of a stream producer, several stream
transformation operations and a stream consumer. All these operations taken
together form a closed loop (like a for or while loop) processing the stream
elements. Elements are transferred between stages using a boxed data
constructor. However, all the stages of the pipeline are "fused" together by
GHC, eliminating the boxing of intermediate constructors, and thus forming a
tight C like loop without any boxed data being used in the loop.

Stream fusion works effectively when:

* the stream pipeline is composed statically (known at compile time)
* all the operations forming the loop are inlined
* the loop is not recursively defined, recursion breaks inlining

If these conditions cannot be met, the CPS style stream type 'StreamK' may
turn out to be a better choice than the fused stream type 'Stream'.

## Stream vs StreamK

The fused stream model avoids constructor allocations and function call
overheads. However, the stream is represented as a state machine, and to
generate stream elements it has to navigate the decision tree of the state
machine. Moreover, the state machine is cranked for each element in the stream.
This performs extremely well when the number of states are limited. The state
machine starts getting expensive as the number of states increase. For example,
generating a stream from a list requires a single state and is very efficient,
even if it has millions of elements, there is only one state machine. However,
using 'cons' to construct a million element stream would be a disaster because
it is statically fusing a million state machines.

A typical worst case scenario for fused stream model is a large number of
`cons` or `append` operations. A few static `cons` or `append` operations
are very fast, much faster than a CPS style stream because CPS involves a
function call for each element whereas fused stream involves a few
conditional branches in the state machine. However, constructing a large
stream using `cons` introduces as many states in the state machine as the
number of elements. If we compose `cons` as a balanced binary tree it will
take @n * log n@ time to navigate the tree, and @n * n@ if it is a right
associative composition.

Operations like 'cons' or 'append' are typically recursively called to
construct a lazy infinite stream. For such use cases the CPS style 'StreamK'
should be used. CPS streams do not use an explicit state machine that needs to be
cranked for each element, past state has no effect on the future element
processing. However, CPS incurs a function call overhead for each element
processed, the overhead could be large compared to a fused state machine
even if it has many states. However, because of its linear performance
characteristics, after a certain threshold of stream compositions the CPS
stream would perform much better than the quadratic fused stream operations.

As a general guideline, you need to use 'StreamK' when you have to use
'cons', 'append' or other operations having quadratic complexity at a large
scale. Typically, in such cases you need to compose the stream recursively,
by calling an operation in a loop. The decision to compose the stream is
taken at run time rather than statically at compile time.

Typically you would compose a 'StreamK' of chunks of data so that the StreamK
function call overhead is mitigated, and then process each chunk using 'Stream'
type operations by using statically fused stream pipeline operations on the
chunks.

'Stream' and 'StreamK' types can be interconverted. See
"Streamly.Data.StreamK" module for conversion operations.

## Fold Fusion

Folds support stream fusion for generating loops comparable to the speed of
C. However, it has some limitations. For fusion to work, the folds must be
inlined, folds must be statically known and not generated dynamically, folds
should not be passed recursively.

Another limitation is due to the quadratic complexity causing slowdown when
too many nested compositions are used. Especially, the performance of the
Applicative instance and splitting operations (e.g. 'splitWith') degrades
quadratically (O(n^2)) when combined @n@ times, roughly 8 or less sequenced
operations are fine. For these cases folds can be converted to parsers and
then used as ParserK.