Extending fold/build fusion

[Dan Doel]

To answer myself some after having fiddled with this more....

The failure-to-fuse is apparently only an issue if I put the fusible thing
in the same module as the combinators, for reasons I can't explain. If a
separate module imports and defines bar, things fuse fine.

I'm still not sure what to do about the weird nil-passing definitions. I
came up with one possibility, which is to create a different build:


    nilWrap :: b -> Wrap (Simple b) b
    nilWrap z = Wrap (\(Simple s) e r -> s e r) (\u -> Simple $ \e _ -> u e
z)

    buildPlain :: (forall b f. Wrap f b -> (a -> b -> b) -> b -> b) -> [a]
    buildPlain g = g (nilWrap []) (:) []

This uses the wrapping to plug in the same nil case at every step, which
eliminates the extra argument when used. But, I don't think this is usable.
Some definitions are okay with this wrapper, but others aren't, and I
believe that foldrW/buildW fusion can cause it to get into places where it
isn't okay. For instance, if we use nilWrap in foldr, then:

    foldr f z (reverse xs)

does the wrong thing.


On Thu, Sep 4, 2014 at 5:20 PM, Dan Doel <dan.doel at gmail.com> wrote:

> I've been looking into this a bit in the past day or so, and I feel like
> some of the stuff in the repository doesn't make sense (to me, at least).
>
> For instance, if you start examining the generated code, you'll see quirks
> like, taking map as an example:
>
>     map f xs = go xs []
>       where
>       go xs n = case xs of
>         [] -> n
>         y:ys -> f y : go ys n
>
> In other words, the loop passes along the empty list in an argument for
> the base case, which is a waste. This stems from the definition of foldrW:
>
>     foldrW (Wrap wrap unwrap) f z0 list0 = wrap go list0 z0
>       where
>       go = unwrap $ \list z' -> case list of
>         [] -> z'
>         x:xs -> f x $ wrap go xs z'
>
> Specifically, the z' becomes this extra threaded argument, and never
> disappears. It is possible to fix this by changing the definition of foldrW
> to be:
>
>     ...
>         [] -> z0
>     ...
>
> And ghc then recognizes that the z' being threaded is useless and
> eliminates it. But this raises the question of why it's being threaded this
> way in the first place. It seems like the types in Wrap are inappropriate
> in some way, at least for the general case. But I'm not yet certain what
> they should be.
>
> There are also fusion problems with the current implementation that
> neither I nor David have fully figured out yet. For instance:
>
>     bar = map (+1) (eft 0 1000)
>
> does not fuse, even after trying many tweaks to the definitions (due to
> the eft 0 1000 being pulled out into a let for reasons we don't yet
> understand; it even happens with -fno-full-laziness). However:
>
>     bar = foldl (+) 0 (map (+1) (eft 0 1000))
>
> fuses fully. The only way to fix the former I've yet found is making
> buildW CONLIKE, but that may not be appropriate in general (probably
> isn't). I have a sneaking suspicion that the strangeness mentioned in the
> first part of this mail may be a contributing factor to this latter issue,
> too.
>
> -- Dan
>
>
> On Wed, Sep 3, 2014 at 3:47 PM, Joachim Breitner <mail at joachim-breitner.de
> > wrote:
>
>> Dear Akio,
>>
>>
>> Am Mittwoch, den 12.03.2014, 19:36 +0100 schrieb Joachim Breitner:
>> > Dear Akio,
>> >
>> > Am Dienstag, den 11.02.2014, 08:04 +0900 schrieb Akio Takano:
>> > > I modified the base library to use foldrW/buildW, with no changes to
>> > > foldl yet. nofib showed a very big regression in cryptarithm2, so I'm
>> > > looking into it.
>> >
>> > any news on this front? Did you find out what happened in cryptarithm2?
>> > Do you need help with that?
>>
>> I haven’t heard from you in quite some time. Are you still on this
>> project?
>>
>> Recent investigations into fusion by David Feuer has increased interest
>> in your approach (https://ghc.haskell.org/trac/ghc/ticket/9545).
>>
>> Greetings,
>> Joachim
>>
>>
>> --
>> Joachim “nomeata” Breitner
>>   mail at joachim-breitner.de • http://www.joachim-breitner.de/
>>   Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0xF0FBF51F
>>   Debian Developer: nomeata at debian.org
>>
>>
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://www.haskell.org/mailman/listinfo/ghc-devs
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140905/add583d6/attachment.html>