Strict fold vs regular fold

foldl-vs-foldl-strict.md

Duet's folds example

Duet has this folding example:

data List a = Nil | Cons a (List a)
foldr = \f z l ->
  case l of
    Nil -> z
    Cons x xs -> f x (foldr f z xs)
foldl = \f z l ->
  case l of
    Nil -> z
    Cons x xs -> foldl f (f z x) xs
list = (Cons True (Cons False Nil))
main = foldr _f _nil list

Which can be viewed on here. Set the output to "Concise output".

Regular foldl

Example:

main = foldl _f _nil list

foldl _f _nil list
foldl _f (_f _nil True) (Cons False Nil)
foldl _f (_f (_f _nil True) False) Nil
_f (_f _nil True) False

The foldl computation finished without ever running the _f function. So we are building up nested "thunks", O(n), to be precise, by the size of the input list.

Strict fold (on Integer)

To make a strict fold, we need a way to force evaluation before the recursion step, like this:

foldlS :: (Integer -> b -> Integer) -> Integer -> List b -> Integer
foldlS = \f z l ->
  case l of
    Nil -> z
    Cons x xs -> 
      case f z x of 
        0 -> foldlS f 0 xs
        r -> foldlS f r xs

The foldS is specific to integer on the return type of f, so we can force its result with a case. In real Haskell, we have the ! pattern syntax to do the same for any type, but Duet doesn't have it. In the evaluation steps you can see it stops evaluation when it reaches the case, as _foo is syntax in Duet for a "hole".

Strict fold vs regular fold

So, comparing foldl with the strict fold foldS, we get:

list = (Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil))))
main = foldl (\x y -> x + y) 0 list

foldl (\x y -> x + y) 0 list
((\x y -> x + y) ((\x y -> x + y) ((\x y -> x + y) 0 1) 2) 3) + 4
((\y -> ((\x y -> x + y) ((\x y -> x + y) 0 1) 2) + y) 3) + 4
(((\x y -> x + y) ((\x y -> x + y) 0 1) 2) + 3) + 4
(((\y -> ((\x y -> x + y) 0 1) + y) 2) + 3) + 4
((((\x y -> x + y) 0 1) + 2) + 3) + 4
((((\y -> 0 + y) 1) + 2) + 3) + 4
(((0 + 1) + 2) + 3) + 4
((1 + 2) + 3) + 4
(3 + 3) + 4
6 + 4
10

versus

list = (Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil))))
main = foldl (\x y -> x + y) 0 list

foldlS (\x y -> x + y) 0 list
foldlS (\x y -> x + y) 1 (Cons 2 (Cons 3 (Cons 4 Nil)))
foldlS (\x y -> x + y) 3 (Cons 3 (Cons 4 Nil))
foldlS (\x y -> x + y) 6 (Cons 4 Nil)
foldlS (\x y -> x + y) 10 Nil
10

You can see the accumulated number z as 0, 1, 3, 6, 10. Whereas in foldl you see a thunk of (((0 + 1) + 2) + 3) + 4 accumulated. foldS is therefore far more efficient.