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@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@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@joachim-breitner.de • http://www.joachim-breitner.de/
Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F
Debian Developer: nomeata@debian.org

_______________________________________________
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs