What is Haskell's Stream Fusion

Question

What is Haskell's Stream Fusion and how do I use it?

Answer 1

Is there something that you need to know which is not already covered in this post? If so, can you be more specific?

Answer 2

This is about as a definitive answer as you can get.

Answer 3

The paper that Logan points to is great, but it's a little difficult. (Just ask my students.) It's also a great deal about 'how stream fusion works' and only a fraction 'what stream fusion is and how you can use it'.

The problem that stream fusion solves is that functional codes as written often allocate intermediate lists, e.g., to create an infinite list of node numbers, you might write

nodenames = map ("n"++) $ map show [1..]

Naive code would allocate an infinite list of integers [1, 2, 3, ...], an infinite list of strings ["1", "2", "3", ...], and eventually an infinite list of names ["n1", "n2", "n3", ...]. That's too much allocation.

What stream fusion does is translate a definition like nodenames into something which uses a recursive function that allocates only what is needed for the result. In general, eliminating allocation of intermediate lists is called deforestation.

To use stream fusion, you need to write non-recursive list functions that use the functions from the stream-fusion library described in GHC ticket 915 (map, foldr, and so on) instead of explicit recursion. This library contains new versions of all the Prelude functions which have been rewritten to exploit stream fusion. Apparently this stuff is slated to make it into the next GHC release (6.12) but is not in the current stable version (6.10). If you want to use the library Porges has a nice simple explanation in his answer.

If you actually want an explanation of how stream fusion works, post another question---but that's much harder.

Answer 4

Don Stewart wrote a pretty good article here that demonstrates how the uvector library can be used to do stream fusion.

Answer 5

As far as I am aware, and contrary to what Norman said, stream fusion is not currently implemented in GHC's base (ie. you cannot just use Prelude functions). For more information see GHC ticket 915.

To use stream fusion you need to install the stream-fusion library, import Data.List.Stream (you can also import Control.Monad.Stream) and only use functions from that module rather than the Prelude functions. This means importing the Prelude hiding all the default list functions, and not using [x..y] constructs or list comprehension.

Answer 6

Isn’t it correct, that when GHC in 6.12 uses those new functions by default, that they will also implement [x..y] and list comprehensions in that non-recursive manner? Because the only reason they aren’t right row, is that they are internal and not really written in Haskell, but more like keywords, for speed’s sake and/or because you wouldn’t be able to redefine that syntax.