Haskell: More Strict Fold 'with Deepseq

Question

Foldr page Foldl Foldl ' discusses foldl' and defines it as:

 foldl' fz [] = z foldl' fz (x:xs) = let z' = z `f` x in seq z' $ foldl' fz' xs 

This is done in order to avoid space leaks, i.e. therefore, fold' , which produces a constant-sized result, uses only constant space.

However, this does not necessarily work, as indicated here:

The nested seq function only performs the calculation of the topmost constructor. If the drive is a more complex object, then fold' will still accumulate unvalued tricks.

The obvious solution is to change seq to deepseq , as shown (if you are working with NFData ):

 foldl_strict fz [] = z foldl_strict fz (x:xs) = let z' = z `f` x in deepseq z' $ foldl_strict fz' xs 

But I feel this can be terribly inefficient, since the whole structure needs to go through deepseq , each of which goes through a loop (if the compiler cannot statically prove that this is not necessary).

Then I tried this:

 foldl_stricter fzl = deepseq z $ foldl_stricter' fzl foldl_stricter' fz [] = z foldl_stricter' fz (x:xs) = let z' = deepseq x $ z `f` x in seq z' $ foldl_stricter' fz' xs 

But found that this had this problem. Below is an error message when it should return 3.

 foldl_stricter (\xy -> x + head y) 0 [[1..],[2..]] 

So fold_stricter too strict. The list does not have to be strict, which is important to prevent space leaks, because the battery is strict. fold_stricter goes too far and also makes the list strict, leading to a crash above.

Which brings us back to fold_strict . Is deepseq in the data structure of size n time O(n) or only time O(n) for the first time and O(1) after that? (As dbaupp suggests in comment below)

Answer 1

In fact, your two foldl implementations foldl very different. There is no guarantee that fzx will need to go all the way through x in order to calculate its answer, so deepseq x (fzx) may do unnecessary work; furthermore, even if x fully evaluated, there is no guarantee that fzx does not have nested tricks, so let z' = deepseq x (fzx) in seq z' (foo z') may not do enough work.

The correct solution to the problem you indicated is to use foldl' and the strict data type as the type of battery; thus, seq will only need to check the constructor in order to know that the whole structure is fully appreciated, and, conversely, forcing the constructor will lead to a full evaluation of the entire structure.