<div dir="ltr"><div class="gmail_default" style="font-family:tahoma,sans-serif">Jaro</div><div class="gmail_default" style="font-family:tahoma,sans-serif"><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail_default" style="font-family:tahoma,sans-serif">
1. Is the ‘concatMap’ problem really the only problem left on the way to
using stream fusion instead of foldr/build fusion in base? <br></div></blockquote><div class="gmail_default" style="font-family:tahoma,sans-serif"><br></div><div class="gmail_default" style="font-family:tahoma,sans-serif">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?</div><div class="gmail_default" style="font-family:tahoma,sans-serif"><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail_default" style="font-family:tahoma,sans-serif">
concatMap (λx → Stream next (f x)) = concatMap' next f
</div></blockquote><div><br></div><div style="font-family:tahoma,sans-serif" class="gmail_default">If it was lined up nicely like that it'd be easy. But what about</div><div style="font-family:tahoma,sans-serif" class="gmail_default"><br></div><div style="font-family:tahoma,sans-serif;margin-left:40px" class="gmail_default">concatMap (\x. Stream next (x*2 +x))</div><div style="font-family:tahoma,sans-serif;margin-left:40px" class="gmail_default"><br></div><div style="font-family:tahoma,sans-serif" class="gmail_default">Then you want matching to succeed, with the substitution</div><div style="font-family:tahoma,sans-serif;margin-left:40px" class="gmail_default">f :-> (\p. p*2 +p)</div><div style="font-family:tahoma,sans-serif;margin-left:40px" class="gmail_default"><br></div><div style="font-family:tahoma,sans-serif" class="gmail_default">This is called "higher order matching" and is pretty tricky. You could start with <a href="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" target="_blank">this paper</a>.</div><div style="font-family:tahoma,sans-serif" class="gmail_default"><br></div><div style="font-family:tahoma,sans-serif" class="gmail_default"><a href="https://gitlab.haskell.org/ghc/ghc/-/issues/22361#note_460918" target="_blank">My comment </a>on #22361 also refers to the potential usefulness of higher order matching.</div><div style="font-family:tahoma,sans-serif" class="gmail_default"><br></div><div style="font-family:tahoma,sans-serif" class="gmail_default">Simon<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, 14 Nov 2022 at 09:47, J. Reinders <<a href="mailto:jaro.reinders@gmail.com" target="_blank">jaro.reinders@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dear GHC devs,<br>
<br>
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.<br>
<br>
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?<br>
<br>
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.<br>
<br>
However, Duncan Coutts proposed in his thesis to make rewrite rules slightly more powerful and use the rewrite rule:<br>
<br>
concatMap (λx → Stream next (f x)) = concatMap' next f<br>
<br>
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.<br>
<br>
So my main questions are:<br>
<br>
1. Is the ‘concatMap’ problem really the only problem left on the way to using stream fusion instead of foldr/build fusion in base?<br>
<br>
2. Has the rewrite rule approach to solving the ‘concatMap’ problem ever been tried?<br>
<br>
Any other information about the current status of stream fusion is also much appreciated.<br>
<br>
Cheers,<br>
<br>
Jaro Reinders<br>
<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div>