Extending fold/build fusion

[Akio Takano]

On Thu, Jan 16, 2014 at 4:20 AM, Simon Peyton Jones
<simonpj at microsoft.com> wrote:
>
> Akio
>
>
>
> Aha!  So you are really talking about replacing the *entire* foldr/build story with a new one, namely a foldW/buildW story.  Presumably all producers and consumers (map, filter, take, drop etc) must be redefined using foldW and buildW instead of fold and build.  Is that right?


Yes

>
>
>
> That is much more significant than the wiki page describes.  If you are serious about this, could you perhaps update the wiki page to describe what you propose?   Do you believe that the new story will catch every case that the old one does?  (Plus some new ones.)  Does your data support that?


I updated the file. Please see the section "Will the functions
currently fusible continue to fuse well?"

https://github.com/takano-akio/ww-fusion#will-the-functions-currently-fusible-continue-to-fuse-well

>
>
>
> I’m really not sure about your Tree example.   I agree that the foldl’ style code gives the result that you show.  But I tried the more straightforward version:
>
> sumT :: Tree -> Int
>
> sumT t = foldr (+) 0 (build (toListFB t))
>
>
>
> This yielded pretty decent code:
>
> FB.$wgo =
>
>   \ (w_sio :: FB.Tree) (ww_sir :: GHC.Prim.Int#) ->
>
>     case w_sio of _ {
>
>       FB.Tip rb_dgM -> GHC.Prim.+# rb_dgM ww_sir;
>
>       FB.Bin x_af0 y_af1 ->
>
>         case FB.$wgo y_af1 ww_sir of ww1_siv { __DEFAULT ->
>
>         FB.$wgo x_af0 ww1_siv
>
>         }
>
>     }
>
>
>
> This builds no thunks.  It does build stack equal to the depth of the tree.  But your desired go1 code will also do exactly the same; go1 is strict in its second argument and hence will use call-by-value, and hence will build stack equal to the depth of the tree.

I don't think using foldr is a general replacement for foldl', because
(1) it is less efficient when the input is a list and (2) it will
change the meaning of the code when the operator to fold with is not
associative.

-- Akio

>
>
>
> In short, I’m not yet seeing a benefit.
>
> I am probably missing something important.
>
> Suggestion: rather than just reply to this email (soon lost in the email stream), it would be easier for others to join in if you updated your wiki page to say (a) what you propose, and (b) how it can yield benefits that the current setup cannot.  Then an email reply can say “go look at section 3” or whatever.
>
>
>
> best wishes
>
>
>
> Simon
>