How exactly does Stream Fusion work?

functional-programming, haskell

Solution

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.

Problem

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?

Original source