Extending fold/build fusion

[Akio Takano]

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/20140103/f9b3853b/attachment.html>