Extending fold/build fusion

[Akio Takano]

On Fri, Jan 31, 2014 at 6:18 PM, Joachim Breitner
<mail at joachim-breitner.de> wrote:
> Dear Akio,
>
> Am Freitag, den 31.01.2014, 16:54 +0900 schrieb Akio Takano:
>> > Can you implement build via buildW, so that existing code like
>> >   "map"  [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
>> > can be used unmodified? But probably not... but that would mean a
>> > noticeable incompatibility and a burden on library authors using list
>> > fusion.
>>
>> You can implement build in terms of buildW. However any list producer
>> defined using that definition of build would produce good code if the
>> final consumer is a left fold. The resulting code will be in CPS. On
>> the other hand, I imagine that if we also annotate foldl with oneShot,
>> this problem may become less severe.
>
> Hmm, I guess my question was not precise enough. Let me rephrase: To
> what extend can you provide the exsting foldr/build API _without_ losing
> the advantages of your approach?

Sorry, I had a bad typo in the previous message: I meant

Any list producer defined using that definition of build would *not*
produce good code if the final consumer is a left fold.

To answer your question: list producers defined using build will
continue to compile, but will *not* be able to take any advantages of
foldrW/buildW.

>
> Or put differently: Could you add a section to the wiki that serves as a
> migration guide to those who want to port their producers and consumers
> to your system, without having to fully understand what's going on?

I added a section for this:

https://github.com/takano-akio/ww-fusion#how-to-make-a-list-produer-work-with-foldrwbuildw-fusion

>
>
> Another thing that would be very interesting: Your framework seems to be
> quite general: Are there other useful worker-wrapper-transformations
> that one would possibly want to apply to a fused computations, besides
> the one that makes foldl work well? Other examples of
> w/w-transformations in GHC include
>  * Unboxing of parameters
>  * Unboxing of return values, returning multiple values
> but maybe you can think of other interesting examples.

I can't think of anything new, but I think it's often interesting to
do a (nested) CPR transformation for a fused function. I added such an
example (see serializeTree and foldIO_Ptr) :

https://github.com/takano-akio/ww-fusion/blob/master/test.hs#L23

However this kind of tricks may become unnecessary once GHC starts to
do nested CPRs.

>
> Am I right that the _consumer_ of a fused computation decides which
> worker-wrapper pair to use?

Yes.

>
>
> I still quite like the approach, mostly because it does so well for
> lists. I still have to fully grok it, though :-)
>
> Greetings,
> Joachim
>
>
> --
> Joachim Breitner
>   e-Mail: mail at joachim-breitner.de
>   Homepage: http://www.joachim-breitner.de
>   Jabber-ID: nomeata at joachim-breitner.de
>