Миран Липовача - Изучай Haskell во имя добра!

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].

Взгляд на свёртки как на последовательное применение функции к элементам списка помогает понять, почему правая свёртка иногда отлично работает с бесконечными списками. Давайте реализуем функцию andс помощью foldr, а потом выпишем последовательность применений, как мы это делали в предыдущих примерах. Тогда мы увидим, как ленивость языка Haskell позволяет правой свёртке обрабатывать бесконечные списки.

Функция andпринимает список значений типа Boolи возвращает False, если хотя бы один из элементов равен False; в противном случае она возвращает True. Мы будем обходить список справа, используя Trueкак начальное значение. В качестве бинарной функции будем использовать операцию &&, потому что должны вернуть Trueтолько в том случае, когда все элементы списка истинны. Функция &&возвращает False, если хотя бы один из параметров равен False, поэтому если мы встретим в списке False, то аккумулятор будет установлен в значение Falseи окончательный результат также будет False, даже если среди оставшихся элементов списка обнаружатся истинные значения.

and' :: [Bool] -> Bool

and' xs = foldr (&&) True xs

Зная, как работает foldr, мы видим, что выражение and' [True,False,True]будет вычисляться следующим образом:

True && (False && (True && True))

Последнее Trueздесь – это начальное значение аккумулятора, тогда как первые три логических значения взяты из списка [True,False,True]. Если мы попробуем вычислить результат этого выражения, получится False.

А что если попробовать то же самое с бесконечным списком, скажем, repeat False? Если мы выпишем соответствующие применения, то получится вот что:

False && (False && (False && (False …

Ленивость Haskell позволит вычислить только то, что действительно необходимо. Функция &&устроена таким образом, что если её первый параметр False, то второй просто игнорируется, поскольку и так ясно, что результат должен быть False.

Функция foldrбудет работать с бесконечными списками, если бинарная функция, которую мы ей передаём, не требует обязательного вычисления второго параметра, если значения первого ей достаточно для вычисления результата. Такова функция &&– ей неважно, каков второй параметр, при условии, что первый — False.

Функции scanlи scanrпохожи на foldlи foldr, только они сохраняют все промежуточные значения аккумулятора в список. Также существуют функции scanl1и scanr1, которые являются аналогами foldl1и foldr1.

ghci> scanl (+) 0 [3,5,2,1]

[0,3,8,10,11]

ghci> scanr (+) 0 [3,5,2,1]

[11,8,3,1,0]

ghci> scanl1 (\acc x –> if x > acc then x else acc) [3,4,5,3,7,9,2,1]

[3,4,5,5,7,9,9,9]

ghci> scanl (flip (:)) [] [3,2,1]

[[],[3],[2,3],[1,2,3]]

При использовании функции scanlфинальный результат окажется в последнем элементе итогового списка, тогда как функция scanrпоместит результат в первый элемент.

Функции сканирования используются для того, чтобы увидеть, как работают функции, которые можно реализовать как свёртки. Давайте ответим на вопрос: как много корней натуральных чисел нам потребуется, чтобы их сумма превысила 1000? Чтобы получить сумму квадратов натуральных чисел, воспользуемся map sqrt [1..]. Теперь, чтобы получить сумму, прибегнем к помощи свёртки, но поскольку нам интересно знать, как увеличивается сумма, будем вызывать функцию scanl1. После вызова scanl1посмотрим, сколько элементов не превышают 1000. Первый элемент в результате работы функции scanl1должен быть равен единице. Второй будет равен 1 плюс квадратный корень двух. Третий элемент – это корень трёх плюс второй элемент. Если у нас x сумм меньших 1000, то нам потребовалось ( x +1) элементов, чтобы превзойти 1000.