foldl-1.0.0: Composable, streaming, and efficient left folds

I'm releasing the foldl library, which builds upon this previous post of mine. This library lets you build and combine multiple folds that traverse streams in constant memory.

I will begin using the same example from the previous post: computing an average. The naive version would be written like this:

average :: [Int] -> Int
average xs = sum xs `div` length xs

This does not work well because it:

• loads the entire list into memory, and:
• cannot fuse away the intermediate list.

We can improve on this using foldl where we will compute the average by combining a sum fold with a length fold, using Applicative style:

import Control.Applicative
import qualified Control.Foldl as L

average :: L.Fold Int Int
average = div <$> L.sum <*> L.length

All folds built this way have two nice properties which foldl guarantees:

• They only traverse the list once
• They will not leak space

We can use fold to apply this combined fold to the list:

main = print $ L.fold average [0..100000000]

This gives good efficiency at about 1 nanosecond per list element because it fuses away the intermediate list:

500000000

real 0m0.956s
user 0m0.952s
sys 0m0.000s

We can see this if we inspect the core, too, which produces this reasonably tight loop (which I've cleaned up):

$wgo =
  \ (x :: Int#)
    (y :: Int#)      -- y is keeping tally of the sum
    (z :: Int#) ->   -- z is keeping tally of the length
    case x of x' {
      __DEFAULT ->
        $wgo
          (x' +# 1 )
          (y  +# x')
          (z  +# 1 );
      1000000000 ->
        (# I# (y +# 1000000000),
           I# (z +# 1) #)
    }

This works because fold is implemented in terms of foldr to trigger build/foldr fusion. However, not all lists will fuse this way. I find, for example, that lists of Doubles refuse to fuse in this way:

import Control.Applicative
import qualified Control.Foldl as L

-- This gives worse performance: ~40 ns per step
average :: L.Fold Double Double
average = (/) <$> L.sum <*> L.genericLength

main = print $ L.fold average [0..1000000000]

I haven't yet figured out how to trick GHC into fusing away these lists. If anybody knows how to do this, please contribute a patch.

Fortunately, these folds preserve the original accumulator, step function, and extraction function, so you can always unpack the Fold type and then implement the list fusion yourself:

main = case average of
    L.Fold step start done -> do
        let go n x =
                if (n > 1000000000)
                then x
                else go (n + 1) $! step x n
        print $ done (go 0 start)

So while reliable list fusion is still an unsolved problem, you can still use foldl to get reasonable performance and guarantee no space leaks. Also, there is always the option of using foldl to do the work of assembling derived strict and streaming folds and then implementing list fusion yourself if you want to squeak out every last drop of performance.

I wrote up this library to dispel the myth that only experts can fold things efficiently in Haskell. foldl lets you begin from simple primitive folds that you can fit in your head and then chain them together into complex folds with little effort.