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_460918>on #22361 also refers to the potential usefulness of higher order matching. Simon On Mon, 14 Nov 2022 at 09:47, J. Reinders <[email protected]> wrote: > 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 > [email protected] > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >
_______________________________________________ ghc-devs mailing list [email protected] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
