Author: Eiko

Time: 2025-04-11 07:30:27 - 2025-04-11 07:30:27 (UTC)

Protagonists: foldl, foldr, foldl'

Their original definitions are

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f acc []     = acc
foldl f acc (x:xs) = foldl f (acc `f` x) xs
-- (((1 `f` 2) `f` 3) `f` 4) `f` 5

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs
-- 1 `f` (2 `f` (3 `f` (4 `f` (5 `f` z))))

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f acc []      = acc
foldl' f !acc (x:xs) = foldl' f (acc `f` x) xs
-- (((1 `f` 2)! `f` 3)! `f` 4)! `f` 5

Translate to STG

which translates to the following stg code

foldl = \f acc xs ->
  case xs of
    [] -> acc
    (x:xs) -> let inner = \(f acc x) -> f acc x
              in foldl f inner xs

foldr = \f z xs ->
  case xs of
    [] -> z
    (x:xs) -> let rest = \(f z xs) -> foldr f z xs
              in f x rest

foldl' = \f acc xs ->
  case xs of
    [] -> acc
    (x:xs) -> case f acc x of
      acc' -> foldl' f acc' xs

Experiment Result

Of summing [1..10] shows that

• foldl' evaluates sum correctly without consuming much heap or stack.

• foldr uses excessive amount of stack.

• foldl uses both excessive amount of stack and heap.

Analysis of the result

• We know that in stg, case corresponds to evaluation, let corresponds to allocation.

• A large number of nested case would consume stack

• A large number of let statements would consume heap

• When evaluating (((1 + 2) + 3) + 4) + 5 in foldl and foldl', it will be turned into

  let acc1 = (1+2)
  in foldl (+) acc1 [3,4,5] 
  
  let acc1 = (1+2)
  in  let acc2 = acc1 + 3
      in  foldl (+) acc2 [4,5] 
  
  let acc1 = (1+2)
  in  let acc2 = acc1 + 3
      in  let acc3 = acc2 + 4
          in  foldl (+) acc3 [5] 
  
  let acc1 = (1+2)
  in  let acc2 = acc1 + 3
      in  let acc3 = acc2 + 4
          in  let acc4 = acc3 + 5
              in foldl (+) acc4 [] 
  
  let acc1 = (1+2)
  in  let acc2 = acc1 + 3
      in  let acc3 = acc2 + 4
          in  let acc4 = acc3 + 5
              in  acc4

  The process of building up this expression itself does not consume excessive stack, but when we start to evaluate it, since evaluating acc4 requires evaluating acc3, and so on, we will have to do nested evaluation.