Status of Stream Fusion?

[J. Reinders]

Dear GHC devs,

I’m interested in stream fusion and would like to see what it takes to fix the remaining issues, so that it can replace foldr/build fusion in base.

First of all I would like to know what exactly the challenges are that are left. I believe one of the main remaining problems is the fusion of ‘concatMap’. Is that really the only thing?

Secondly, I would like to know what has already been tried. I know Sebastian Graf has spent a lot of effort trying to get SpecConstr to work on lambda arguments without success. I’ve read that Sebastian now considers the static argument transformation more promising.

However, Duncan Coutts proposed in his thesis to make rewrite rules slightly more powerful and use the rewrite rule:

    concatMap (λx → Stream next (f x)) = concatMap' next f

Has that ever been tried? If so, what is the problem with this rewrite rule approach? I can understand that the `f x` function application is usually in a more reduced form, but it seems relatively easy to make the rewrite rule matcher smart enough to see through beta-reductions like that.

So my main questions are:

1. Is the ‘concatMap’ problem really the only problem left on the way to using stream fusion instead of foldr/build fusion in base?

2. Has the rewrite rule approach to solving the ‘concatMap’ problem ever been tried?

Any other information about the current status of stream fusion is also much appreciated.

Cheers,

Jaro Reinders