Extending fold/build fusion

[Carter Schonwald]

Hey akio, it's certainly an interesting idea.

If you implement it, the first step would be to run a nofib before and
after to benchmark the impact of the change.

On Thursday, January 9, 2014, Akio Takano wrote:

> 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<javascript:_e({}, 'cvml', '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/20140109/3fe05cfb/attachment.html>