RE: Extending fold/build fusion

I've hesitated to reply, because I have lots of questions but no time to investigate in. I'm looking at your wiki page https://github.com/takano-akio/ww-fusion * Does your proposed new fold' run faster than the old one? You give no data. * The new foldl' is not a "good consumer" in the foldr/build sense, which a big loss. What if you say fold' k z [1..n]; you want the intermediate list to vanish. * My brain is too small to truly understand your idea. But since foldrW is non-recursive, what happens if you inline foldrW into fold', and then simplify? I'm betting you get something pretty similar to the old foldl'. Try in by hand, and with GHC and let's see the final optimised code. * Under "motivation" you say "GHC generates something essentially like..." and then give some code. Now, if GHC would only eta-expand 'go' with a second argument, you'd get brilliant code. And maybe that would help lots of programs, not just this one. It's a slight delicate transformation but I've often thought we should try it; c.f #7994, #5809 Simon From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of Akio Takano Sent: 09 January 2014 13:25 To: ghc-devs Subject: Re: Extending fold/build fusion Any input on this is appreciated. In particular, I'd like to know: if I implement the idea as a patch to the base package, is there a chance it is considered for merge? -- Takano Akio On Fri, Jan 3, 2014 at 11:20 PM, Akio Takano mailto:tkn.akio@gmail.com> wrote: Hi, I have been thinking about how foldl' can be turned into a good consumer, and I came up with something that I thought would work. So I'd like to ask for opinions from the ghc devs: if this idea looks good, if it is a known bad idea, if there is a better way to do it, etc. The main idea is to have an extended version of foldr: -- | A mapping between @a@ and @b@. data Wrap a b = Wrap (a -> b) (b -> a) foldrW :: (forall e. Wrap (f e) (e -> b -> b)) -> (a -> b -> b) -> b -> [a] -> b 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' This allows the user to apply an arbitrary "worker-wrapper" transformation to the loop. Using this, foldl' can be defined as newtype Simple b e = Simple { runSimple :: e -> b -> b } foldl' :: (b -> a -> b) -> b -> [a] -> b foldl' f initial xs = foldrW (Wrap wrap unwrap) g id xs initial where wrap (Simple s) e k a = k $ s e a unwrap u = Simple $ \e -> u e id g x next acc = next $! f acc x The wrap and unwrap functions here ensure that foldl' gets compiled into a loop that returns a value of 'b', rather than a function 'b -> b', effectively un-CPS-transforming the loop. I put preliminary code and some more explanation on Github: https://github.com/takano-akio/ww-fusion Thank you, Takano Akio