Иной взгляд на свёртки

Есть ещё один способ представить работу правой и левой свёртки. Скажем, мы выполняем правую свёртку с бинарной функцией f и стартовым значением z. Если мы применяем правую свёртку к списку [3,4,5,6], то на самом деле вычисляем вот что:

f 3 (f 4 (f 5 (f 6 z)))

Функция f вызывается с последним элементом в списке и аккумулятором; получившееся значение передаётся в качестве аккумулятора при вызове функции с предыдущим значением, и т. д. Если мы примем функцию f за операцию сложения и начальное значение за нуль, наш пример преобразуется так:

3 + (4 + (5 + (6 + 0)))

Или, если записать оператор + как префиксную функцию, получится:

(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))

Аналогичным образом левая свёртка с бинарной функцией g и аккумулятором z является эквивалентом выражения

g (g (g (g z 3) 4) 5) 6

Если заменить бинарную функцию на flip (:) и использовать [] как аккумулятор (выполняем обращение списка), подобная запись эквивалентна следующей:

flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6

Если вычислить это выражение, мы получим [6,5,4,3].