Status of Stream Fusion?

[Simon Peyton Jones]

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 <jaro.reinders at gmail.com> 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
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20221114/811da987/attachment.html>