foldl as foldr to get list fusion

13 Oct 2011

      Hello,

Is there any reason other than history that foldl and foldl' are not
defined in terms of foldr?

If we define them in terms of foldr like:

foldl f z xs = foldr (\x y -> \z' -> let z'' = z' `f` x in y z'') id xs z
{-# INLINE foldl #-}

foldl' f z xs = foldr (\x y -> \z' -> let !z'' = z' `f` x in y z'') id xs z
{-# INLINE foldl' #-}

we can benefit from list fusion.

For example if we define sum as:

sum :: Num a => [a] -> a
sum = foldl (+) 0

then building the following program with -O2:

fuse = sum (replicate 1000000 1 ++ replicate 5000 1 :: [Int])

yields the following totally fused core:

fuse :: Int
fuse = case $wxs 1000000 0 of ww_ssn {
         __DEFAULT -> I# ww_ssn
       }

$wxs :: Int# -> Int# -> Int#
$wxs =
  \ (w_ssg :: Int#) (ww_ssj :: Int#) ->
    case <=# w_ssg 1 of _ {
      False -> $wxs (-# w_ssg 1) (+# ww_ssj 1);
      True  -> $wxs1_rsB 5000 (+# ww_ssj 1)
    }

$wxs1_rsB :: Int# -> Int# -> Int#
$wxs1_rsB =
  \ (w_ss5 :: Int#) (ww_ss8 :: Int#) ->
    case <=# w_ss5 1 of _ {
      False -> $wxs1_rsB (-# w_ss5 1) (+# ww_ss8 1);
      True  -> +# ww_ss8 1
    }

Regards,

Bas

Bas van Dijk

Daniel Fischer

Bas van Dijk

tags

participants (2)