foldl is a loop

This is quite a simple way to think about foldl, which is not a natural fold on lists, but can still be quite useful sometimes. (Geraint Jones calls it loop instead, which is in some ways a much better name.)

Take a look at the foldl function (or one formulation of it):

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

It might be initially unclear what this function is doing exactly - for me, at least, it’s less obvious than foldr.

Here’s a frame for thinking about it: consider the following imperative Python program for converting hexadecimal numbers, using a deque as a stack:

from collections import deque
 
x = 0
def g(x, y): return (x << 4) + y
 
stack = deque([4, 2, 1, 12, 1])
while stack:
    x = g(x, stack.popleft())

The above Python program is analogous to the following in Haskell:

hex :: [Int] -> Int
hex = foldl f v
  where
    f x y = (x * 16) + y
    v = 0

The analogy is that there is a variable (x in the Python program) that is initially set to the value v. Then there is iteration through the stack, each time updating v according to some function, g in the Python and f in the Haskell.