Sun Apr 18 11:09:09 EDT 2010

Stream Fusion

About [1].  Simplified, there is a duality in the way sequences can be
approached: as lists data or as streams (an unfolding of the list, the
list's co-structure).

The natural operation over a list is a fold, while the natural
operation over a stream is an unfold.  A stream is represented as an
initial state and a stepper function.

Fusing co-structures: The key trick is that all stream producers are
non-recursive.  This is established by allowing a stream to produce
`Skip' values and moving the recursion to the `fold' part of a

Converting list ops to stream ops doesn't really perform any fusion on
its own.  However, it transforms the code into a form that is more
accessible to the Haskell deforestation optimizer as it has no
unnecessary recursion that ``blocks the view''.

[1] http://www.cse.unsw.edu.au/~dons/papers/CLS07.html