Jaro 1. Is the ‘concatMap’ problem really the only problem left on the way to
using stream fusion instead of foldr/build fusion in base?
Can you say precisely what you mean by "using stream fusion instead of foldr/build fusion in base"? For example, do you have a prototype library that demonstrates what you intend, all except concatMap? concatMap (λx → Stream next (f x)) = concatMap' next f
If it was lined up nicely like that it'd be easy. But what about
concatMap (\x. Stream next (x*2 +x))
Then you want matching to succeed, with the substitution
f :-> (\p. p*2 +p)
This is called "higher order matching" and is pretty tricky. You could
start with this paper
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwic1-ieua37AhWaQUEAHR1jAdsQFnoECAkQAQ&url=https%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fpii%2FS0304397500004023%2Fpdf%3Fmd5%3D51c502a300bacbdc080276bf7e6b3284%26pid%3D1-s2.0-S0304397500004023-main.pdf&usg=AOvVaw3MWXgJFfA_Sg1kXywCJ7yY
.
My comment https://gitlab.haskell.org/ghc/ghc/-/issues/22361#note_460918on
#22361 also refers to the potential usefulness of higher order matching.
Simon
On Mon, 14 Nov 2022 at 09:47, 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
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs