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

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.

sqrtSums :: Int

sqrtSums = length (takeWhile (< 1000) (scanl1 (+) (map sqrt [1..]))) + 1

ghci> sqrtSums

131

ghci> sum (map sqrt [1..131])

1005.0942035344083

ghci> sum (map sqrt [1..130])

993.6486803921487

Мы задействовали функцию takeWhileвместо filter, потому что последняя не работает на бесконечных списках. В отличие от нас, функция filterне знает, что список возрастает, поэтому мы используем takeWhile, чтобы отсечь список, как только сумма превысит 1000.

Пойдём дальше. Теперь объектом нашего внимания станет оператор $, также называемый аппликатором функций . Прежде всего посмотрим, как он определяется:

($) :: (a –> b) –> a –> b

f $ x = f x

Зачем? Что это за бессмысленный оператор? Это просто применение функции! Верно, почти , но не совсем!.. В то время как обычное применение функции (с пробелом) имеет высший приоритет, оператор $имеет самый низкий приоритет. Применение функции с пробелом левоассоциативно (то есть f a b c i– это то же самое, что (((f a) b) c)), в то время как применение функции при помощи оператора $правоассоциативно.

Всё это прекрасно, но нам-то с того какая польза? Прежде всего оператор $удобен тем, что с ним не приходится записывать много вложенных скобок. Рассмотрим выражение sum (map sqrt [1..130]). Поскольку оператор $имеет самый низкий приоритет, мы можем переписать это выражение как sum $ map sqrt [1..130], сэкономив драгоценные нажатия на клавиши. Когда в функции встречается знак $, выражение справа от него используется как параметр для функции слева от него. Как насчёт sqrt 3 + 4 + 9? Здесь складываются 9, 4и корень из 3. Если мы хотим получить квадратный корень суммы, нам надо написать sqrt (3 + 4 + 9)– или же (в случае использования оператора $) sqrt $ 3 + 4 + 9, потому что у оператора $низший приоритет среди всех операторов. Вот почему вы можете представить символ $как эквивалент записи открывающей скобки с добавлением закрывающей скобки в крайней правой позиции выражения.