How exactly does Stream Fusion work?

Question

The only resources on Stream Fusion I can find are papers introducing it, which aren't really the best learning sources. How exactly does stream fusion work?

More specifially, as this is the part the paper didn't explain well: how are the co-structures generated after the list->stream conversion (ie, maps f . maps g) themselves folded?

Answer 1

Here's the definition of maps from Duncan Coutt's thesis (section 1.4.2):

maps :: (a → b) → Stream a → Stream b
maps f (Stream next0 s0) = Stream next s0
    where
        next s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (f x) s′

Now consider the expression

maps f . maps g

A compiler can inline (.) to get

\x -> maps f (maps g x)

We can see from the definition of Stream that it has only one constructor:

data Stream a = ∃ s . Stream (s → Step a s) s

So the previous result is equivalent to:

\(Stream next0 s) -> maps f (maps g (Stream next0 s))

Inlining maps g, which is safe to do as maps is non-recursive (this is the key insight of stream fusion):

\(Stream next0 s) -> maps f (Stream next1 s)
      where
          next1 s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (g x) s′

Inlining maps f:

\(Stream next0 s) -> Stream next2 s
      where
          next1 s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (g x) s′
          next2 s = case next1 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (f x) s′

Next we can inline next1 into next2 and simplify the case expressions with "case-of-case" - again note that next1 is non-recursive - and delete the now dead next1:

\(Stream next0 s) -> Stream next2 s
      where
          next2 s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (f (g x)) s′

The key point is that these steps are all small optimisations that make sense in isolation and that don't require special compiler knowledge of either stream fusion itself, or the Stream type or maps function.