`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 xsThis does not work well because it:

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

`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.lengthAll folds built this way have two nice properties which

`foldl`guarantees:

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

`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.000sWe 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

`Double`s 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.