Demonstration of short-circuiting left and right folds

short_circuiting_folds.hs

-- short-circuiting folds

import Prelude hiding (foldl, foldr)

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

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

-- This left fold builds up a thunk chain of calls to f
-- for the entire list. Then it starts building up a
-- chain of multiplications, starting from the right.
-- It stops when it hits the zero. Then it does a
-- multiplication of the zero by each of the values to
-- the right of it. This is not a true short-circuit,
-- since it takes time proportional to the entire list.

-- let f = \a x -> if x == 0 then 0 else a * x
-- foldl f 1 [2, 3, 0, 4, 5]
-- foldl f (f 1 2) [3, 0, 4, 5]
-- foldl f (f (f 1 2) 3) [0, 4, 5]
-- foldl f (f (f (f 1 2) 3) 0) [4, 5]
-- foldl f (f (f (f (f 1 2) 3) 0) 4) [5]
-- foldl f (f (f (f (f (f 1 2) 3) 0) 4) 5) []
-- f (f (f (f (f 1 2) 3) 0) 4) 5
-- if 5 == 0 then 0 else f (f (f (f 1 2) 3) 0) 4 * 5
-- f (f (f (f 1 2) 3) 0) 4 * 5
-- (if 4 == 0 then 0 else f (f (f 1 2) 3) 0 * 4) * 5
-- f (f (f 1 2) 3) 0 * 4 * 5
-- (if 0 == 0 then 0 else f (f 1 2) 3 * 0) * 4 * 5
-- 0 * 4 * 5
-- 0 * 5
-- 0

-- This right fold builds a chain of multiplications
-- from the left. It stops when it reaches the zero.
-- it then performs all the multiplications from
-- right to left, starting with the zero. This can be
-- considered a true short-circuit as it runs in
-- time proportional to the number of values to the
-- left of the zero.

-- let f = \x a -> if x == 0 then 0 else x * a
-- foldr f 1 [2, 3, 0, 4, 5]
-- f 2 (foldr f 1 [3, 0, 4, 5])
-- if 2 == 0 then 0 else 2 * foldr f 1 [3, 0, 4, 5]
-- 2 * foldr f 1 [3, 0, 4, 5]
-- 2 * f 3 (foldr f 1 [0, 4, 5])
-- 2 * (if 3 == 0 then 0 else 3 * foldr f 1 [0, 4, 5])
-- 2 * (3 * foldr f 1 [0, 4, 5])
-- 2 * (3 * f 0 (foldr f 1 [4, 5]))
-- 2 * (3 * (if 0 == 0 then 0 else foldr f 1 [4, 5]))
-- 2 * (3 * 0)
-- 2 * 0
-- 0