Extending fold/build fusion

[Simon Peyton Jones]

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 at 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 <tkn.akio at gmail.com<mailto:tkn.akio at 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 at .
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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140113/992bc67d/attachment-0001.html>