Каждая функция в языке Haskell официально может иметь только один параметр. Но мы определяли и использовали функции, которые принимали несколько параметров. Как же такое может быть? Да, это хитрый трюк! Все функции, которые принимали несколько параметров, были каррированы. Функция называется каррированной, если она всегда принимает только один параметр вместо нескольких. Если потом её вызвать, передав этот параметр, то результатом вызова будет новая функция, принимающая уже следующий параметр.

Легче всего объяснить на примере. Возьмём нашего старого друга – функцию max. Если помните, она принимает два параметра и возвращает максимальный из них. Если сделать вызов max 4 5, то вначале будет создана функция, которая принимает один параметр и возвращает 4 или поданный на вход параметр – смотря что больше. Затем значение 5 передаётся в эту новую функцию, и мы получаем желаемый результат. В итоге оказывается, что следующие два вызова эквивалентны:

ghci> max 4 5

5

ghci> (max 4) 5

5

Чтобы понять, как это работает, давайте посмотрим на тип функции max:

ghci> :t max

max :: (Ord a) => a –> a –> a

То же самое можно записать иначе:

max :: (Ord a) => a –> (a –> a)

Прочитать запись можно так: функция max принимает параметр типа a и возвращает (–>) функцию, которая принимает параметр типа a и возвращает значение типа a. Вот почему возвращаемый функцией тип и параметры функции просто разделяются стрелками.

Ну и чем это выгодно для нас? Проще говоря, если мы вызываем функцию и передаём ей не все параметры, то в результате получаем новую функцию, а именно – результат частичного применения исходной функции. Новая функция принимает столько параметров, сколько мы не использовали при вызове оригинальной функции. Частичное применение (или, если угодно, вызов функции не со всеми параметрами) – это изящный способ создания новых функций «на лету»: мы можем передать их другой функции или передать им ещё какие-нибудь параметры.

Посмотрим на эту простую функцию:

multThree :: Int -> Int -> Int -> Int

multThree x y z = x * y * z

Что происходит, если мы вызываем multThree 3 5 9 или ((multThree 3) 5) 9? Сначала значение 3 применяется к multThree, так как они разделены пробелом. Это создаёт функцию, которая принимает один параметр и возвращает новую функцию, умножающую на 3. Затем значение 5 применяется к новой функции, что даёт функцию, которая примет параметр и умножит его уже на 15. Значение 9 применяется к этой функции, и получается результат 135. Вы можете думать о функциях как о маленьких фабриках, которые берут какие-то материалы и что-то производят. Пользуясь такой аналогией, мы даём фабрике multThree число 3, и, вместо того чтобы выдать число, она возвращает нам фабрику немного поменьше. Эта новая фабрика получает число 5 и тоже выдаёт фабрику. Третья фабрика при получении числа 9 производит, наконец, результат — число 135. Вспомним, что тип этой функции может быть записан так:

multThree :: Int -> (Int -> (Int -> Int))

Перед символом –> пишется тип параметра функции; после записывается тип значения, которое функция вернёт. Таким образом, наша функция принимает параметр типа Int и возвращает функцию типа Int -> (Int –> Int). Аналогичным образом эта новая функция принимает параметр типа Int и возвращает функцию типа Int -> Int. Наконец, функция принимает параметр типа Int и возвращает значение того же типа Int.

Рассмотрим пример создания новой функции путём вызова функции с недостаточным числом параметров:

ghci> let multTwoWithNine = multThree 9

ghci> multTwoWithNine 2 3

54

В этом примере выражение multThree 9 возвращает функцию, принимающую два параметра. Мы называем эту функцию multTwoWithNine. Если при её вызове предоставить оба необходимых параметра, то она перемножит их между собой, а затем умножит произведение на 9.

Вызывая функции не со всеми параметрами, мы создаём новые функции «на лету». Допустим, нужно создать функцию, которая принимает число и сравнивает его с константой 100. Можно сделать это так:

compareWithHundred :: Int -> Ordering

compareWithHundred x = compare 100 x

Если мы вызовем функцию с 99, она вернёт значение GT. Довольно просто. Обратите внимание, что параметр x находится с правой стороны в обеих частях определения. Теперь подумаем, что вернёт выражение compare 100. Этот вызов вернёт функцию, которая принимает параметр и сравнивает его с константой 100. Ага-а! Не этого ли мы хотели? Можно переписать функцию следующим образом:

compareWithHundred :: Int -> Ordering

compareWithHundred = compare 100

Объявление типа не изменилось, так как выражение compare 100 возвращает функцию. Функция compare имеет тип (Ord a) => a –> (a –> Ordering). Когда мы применим её к 100, то получим функцию, принимающую целое число и возвращающую значение типа Ordering.

 

Сечения

Инфиксные функции могут быть частично применены при помощи так называемых сечений. Для построения сечения инфиксной функции достаточно поместить её в круглые скобки и предоставить параметр только с одной стороны. Это создаст функцию, которая принимает один параметр и применяет его к стороне с пропущенным операндом. Вот донельзя простой пример:

divideByTen :: (Floating a) => a –> a

divideByTen = (/10)

Вызов, скажем, divideByTen 200 эквивалентен вызову 200 / 10, равно как и (/10) 200:

ghci> divideByTen 200

20.0

ghci> 200 / 10

20.0

ghci> (/10) 200

20.0

А вот функция, которая проверяет, находится ли переданный символ в верхнем регистре:

isUpperAlphanum :: Char –> Bool

isUpperAlphanum = (`elem` ['А'..'Я'])

Единственная особенность при использовании сечений – применение знака «минус». По определению сечений, (–4) – это функция, которая вычитает четыре из переданного числа. В то же время для удобства (–4) означает «минус четыре». Если вы хотите создать функцию, которая вычитает четыре из своего аргумента, выполняйте частичное применение таким образом: (subtract 4).

 

Печать функций

До сих пор мы давали частично применённым функциям имена, после чего добавляли недостающие параметры, чтобы всё-таки посмотреть на результаты. Однако мы ни разу не попробовали напечатать сами функции. Попробуем? Что произойдёт, если мы попробуем выполнить multThree 3 4 в GHCi вместо привязки к имени с помощью ключевого слова let либо передачи другой функции?

ghci> multThree 3 4

:1:0:

  No instance for (Show (a –> a))

    arising from a use of `print' at :1:0–12

  Possible fix: add an instance declaration for (Show (a –> a))

  In the expression: print it

  In a 'do' expression: print it

GHCi сообщает нам, что выражение порождает функцию типа a –> a, но он не знает, как вывести её на экран. Функции не имеют экземпляра класса Show, так что мы не можем получить точное строковое представление функций. Когда мы вводим, скажем, 1 + 1 в терминале GHCi, он сначала вычисляет результат (2), а затем вызывает функцию show для 2, чтобы получить текстовое представление этого числа. Текстовое представление 2 – это строка "2", которая и выводится на экран.

ПРИМЕЧАНИЕ. Удостоверьтесь в том, что вы поняли, как работает каррирование и частичное применение функций, поскольку эти понятия очень важны.

 

Функции могут принимать функции в качестве параметров и возвращать функции в качестве значений. Чтобы проиллюстрировать это, мы собираемся создать функцию, которая принимает функцию, а затем дважды применяет её к чему-нибудь!

applyTwice :: (a –> a) –> a –> a

applyTwice f x = f (f x)

Прежде всего, обратите внимание на объявление типа. Раньше мы не нуждались в скобках, потому что символ –> обладает правой ассоциативностью. Однако здесь скобки обязательны. Они показывают, что первый параметр – это функция, которая принимает параметр некоторого типа и возвращает результат того же типа. Второй параметр имеет тот же тип, что и аргумент функции – как и возвращаемый результат. Мы можем прочитать данное объявление в каррированном стиле, но, чтобы избежать головной боли, просто скажем, что функция принимает два параметра и возвращает результат. Первый параметр – это функция (она имеет тип a –> a), второй параметр имеет тот же тип a. Заметьте, что совершенно неважно, какому типу будет соответствовать типовая переменная a – Int, String или вообще чему угодно – но при этом все значения должны быть одного типа.

ПРИМЕЧАНИЕ. Отныне мы будем говорить, что функция принимает несколько параметров, вопреки тому что в действительности каждая функция принимает только один параметр и возвращает частично применённую функцию. Для простоты будем говорить, что a –> a –> a принимает два параметра, хоть мы и знаем, что происходит «за кулисами».

Тело функции applyTwice достаточно простое. Мы используем параметр f как функцию, применяя её к параметру x (для этого разделяем их пробелом), после чего передаём результат снова в функцию f. Давайте поэкспериментируем с функцией:

ghci> applyTwice (+3) 10

16

ghci> applyTwice (++ " ХА-ХА") "ЭЙ"

"ЭЙ ХА-ХА ХА-ХА"

ghci> applyTwice ("ХА-ХА " ++) "ЭЙ"

"ХА-ХА ХА-ХА ЭЙ"

ghci> applyTwice (multThree 2 2) 9

144

ghci> applyTwice (3:) [1]

[3,3,1]

Красота и полезность частичного применения очевидны. Если наша функция требует передать ей функцию одного аргумента, мы можем частично применить функцию-параметр таким образом, чтобы оставался неопределённым всего один параметр, и затем передать её нашей функции. Например, функция + принимает два параметра; с помощью сечений мы можем частично применить её так, чтобы остался только один.

 

Реализация функции zipWith

Теперь попробуем применить ФВП для реализации очень полезной функции из стандартной библиотеки. Она называется zipWith. Эта функция принимает функцию и два списка, а затем соединяет списки, применяя переданную функцию для соответствующих элементов. Вот как мы её реализуем:

zipWith' :: (a –> b –> c) –> [a] –> [b] –> [c]

zipWith' _ [] _ = []

zipWith' _ _ [] = []

zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

Посмотрите на объявление типа. Первый параметр – это функция, которая принимает два значения и возвращает одно. Параметры этой функции не обязательно должны быть одинакового типа, но могут. Второй и третий параметры – списки. Результат тоже является списком. Первым идёт список элементов типа a, потому что функция сцепления принимает значение типа a в качестве первого параметра. Второй должен быть списком из элементов типа b, потому что второй параметр у связывающей функции имеет тип b. Результат – список элементов типа c. Если объявление функции говорит, что она принимает функцию типа a –> b –> c как параметр, это означает, что она также примет и функцию a –> a –> a, но не наоборот.

ПРИМЕЧАНИЕ. Запомните: когда вы создаёте функции, особенно высших порядков, и не уверены, каким должен быть тип, вы можете попробовать опустить объявление типа, а затем проверить, какой тип выведет язык Haskell, используя команду :t в GHCi.

Устройство данной функции очень похоже на обычную функцию zip. Базовые случаи одинаковы. Единственный дополнительный аргумент – соединяющая функция, но он не влияет на базовые случаи; мы просто используем для него маску подстановки _. Тело функции в последнем образце также очень похоже на функцию zip – разница в том, что она не создаёт пару (x, y), а возвращает f x y. Одна функция высшего порядка может использоваться для решения множества задач, если она достаточно общая. Покажем на небольшом примере, что умеет наша функция zipWith':

ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]

[6,8,7,9]

ghci> zipWith' max [6,3,2,1] [7,3,1,5]

[7,3,2,5]

ghci> zipWith' (++) ["шелдон ", "леонард "] ["купер", "хофстадтер"]

["шелдон купер","леонард хофстадтер"]

ghci> zipWith' (*) (replicate 5 2) [1..]

[2,4,6,8,10]

ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]] [[3,4,6],[9,20,30],[10,12,12]]

Как видите, одна-единственная функция высшего порядка может применяться самыми разными способами.

 

Реализация функции flip

Теперь реализуем ещё одну функцию из стандартной библиотеки, flip. Функция flip принимает функцию и возвращает функцию. Единственное отличие результирующей функции от исходной – первые два параметра переставлены местами. Мы можем реализовать flip следующим образом:

flip' :: (a –> b –> c) –> (b –> a –> c)

flip' f = g

  where g x y = f y x

Читая декларацию типа, мы видим, что функция принимает на вход функцию с параметрами типов a и b и возвращает функцию с параметрами b и a. Так как все функции на самом деле каррированы, вторая пара скобок не нужна, поскольку символ –> правоассоциативен. Тип (a –> b –> c) –> (b –> a –> c) – то же самое, что и тип (a –> b –> c) –> (b –> (a –> c)), а он, в свою очередь, представляет то же самое, что и тип (a –> b –> c) –> b –> a –> c. Мы записали, что g x y = f y x. Если это верно, то верно и следующее: f y x = g x y. Держите это в уме – мы можем реализовать функцию ещё проще.

flip' :: (a –> b –> c) –> b –> a –> c

flip' f y x = f x y

Здесь мы воспользовались тем, что функции каррированы. Когда мы вызываем функцию flip' f без параметров y и x, то получаем функцию, которая принимает два параметра, но переставляет их при вызове. Даже несмотря на то, что такие «перевёрнутые» функции обычно передаются в другие функции, мы можем воспользоваться преимуществами каррирования при создании ФВП, если подумаем наперёд и запишем, каков будет конечный результат при вызове полностью определённых функций.

ghci> zip [1,2,3,4,5,6] "привет"

[(1,'п'),(2,'р'),(3,'и'),(4,'в'),(5,'е'),(6,'т')]

ghci> flip' zip [1,2,3,4,5] "привет"

[('п',1),('р',2),('и',3),('в',4),('е',5),('т',6)]

ghci> zipWith div [2,2..] [10,8,6,4,2]

[0,0,0,0,1]

ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]

[5,4,3,2,1]

Если применить функцию flip' к zip, то мы получим функцию, похожую на zip, за исключением того что элементы первого списка будут оказываться вторыми элементами пар результирующего списка, и наоборот. Функция flip' div делит свой второй параметр на первый, так что если мы передадим ей числа 2 и 10, то результат будет такой же, что и в случае div 10 2.

 

Как функциональные программисты мы редко будем обрабатывать одно значение. Обычно нам хочется сразу взять набор чисел, букв или значений каких-либо иных типов, а затем преобразовать всё это множество для получения результата. В данном разделе будет рассмотрен ряд полезных функций, которые позволяют нам работать с множествами значений.

 

Функция map

Функция map берёт функцию и список и применяет функцию к каждому элементу списка, формируя новый список. Давайте изучим сигнатуру этой функции и посмотрим, как она определена.

map :: (a –> b) –> [a] –> [b]

map _ [] = []

map f (x:xs) = f x : map f xs

Сигнатура функции говорит нам, что функция map принимает на вход функцию, которая вычисляет значение типа b по параметру типа a, список элементов типа a и возвращает список элементов типа b. Интересно, что глядя на сигнатуру функции вы уже можете сказать, что она делает. Функция map – одна из самых универсальных ФВП, и она может использоваться миллионом разных способов. Рассмотрим её в действии:

ghci> map (+3) [1,5,3,1,6]

[4,8,6,4,9]

ghci> map (++ "!") ["БУХ", "БАХ", "ПАФ"]

["БУХ!","БАХ!","ПАФ!"]

ghci> map (replicate 3) [3..6]

[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]

ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]

[[1,4],[9,16,25,36],[49,64]]

ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]

[1,3,6,2,2]

Возможно, вы заметили, что нечто аналогичное можно сделать с помощью генератора списков. Вызов map (+3) [1,5,3,1,6] – это то же самое, что и [x+3 | x <– [1,5,3,1,6]]. Тем не менее использование функции map обеспечивает более читаемый код в случаях, когда вы просто применяете некоторую функцию к списку. Особенно когда применяются отображения к отображениям (map – к результатам выполнения функции map): тогда всё выражение с кучей скобок может стать нечитаемым.

 

Функция filter

Функция filter принимает предикат и список, а затем возвращает список элементов, удовлетворяющих предикату. Предикат – это функция, которая говорит, является ли что-то истиной или ложью, – то есть функция, возвращающая булевское значение. Сигнатура функции и её реализация:

filter :: (a –> Bool) –> [a] –> [a]

filter _ [] = []

filter p (x:xs)

  | p x       = x : filter p xs

  | otherwise = filter p xs

Довольно просто. Если выражение p x истинно, то элемент добавляется к результирующему списку. Если нет – элемент пропускается.

Несколько примеров:

ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]

[5,6,4]

ghci> filter (==3) [1,2,3,4,5]

[3]

ghci> filter even [1..10]

[2,4,6,8,10]

ghci> let notNull x = not (null x) in filter notNull [[1],[],[3,4],[]]

[[1],[3,4]]

ghci> filter (`elem` ['а'..'я']) "тЫ СМЕЕШЬСя, ВЕДЬ я ДрУГой"

"тяярой"

ghci> filter (`elem` ['А'..'Я']) "я Смеюсь, Ведь ты такОЙ же"

"СВОЙ"

Того же самого результата можно достичь, используя генераторы списков и предикаты. Нет какого-либо правила, диктующего вам, когда использовать функции map и filter, а когда – генераторы списков. Вы должны решить, что будет более читаемым, основываясь на коде и контексте. В генераторах списков можно применять несколько предикатов; при использовании функции filter придётся проводить фильтрацию несколько раз или объединять предикаты с помощью логической функции &&. Вот пример:

ghci> filter (<15) (filter even [1..20])

[2,4,6,8,10,12,14]

Здесь мы берём список [1..20] и фильтруем его так, чтобы остались только чётные числа. Затем список передаётся функции filter (<15), которая избавляет нас от чисел 15 и больше. Вот версия с генератором списка:

ghci> [ x | x <- [1..20], x < 15, even x]

[2,4,6,8,10,12,14]

Мы используем генератор для извлечения элементов из списка [1..20], а затем указываем условия, которым должны удовлетворять элементы результирующего списка.

Помните нашу функцию быстрой сортировки (см. предыдущую главу, раздел «Сортируем, быстро!»)? Мы использовали генераторы списков для фильтрации элементов меньших (или равных) и больших, чем опорный элемент. Той же функциональности можно добиться и более понятным способом, используя функцию filter:

quicksort :: (Ord a) => [a] –> [a]

quicksort [] = []

quicksort (x:xs) =

  let smallerSorted = quicksort (filter (<= x) xs)

      biggerSorted = quicksort (filter (> x) xs)

  in  smallerSorted ++ [x] ++ biggerSorted

 

Ещё немного примеров использования map и filter

Давайте найдём наибольшее число меньше 100 000, которое делится на число 3829 без остатка. Для этого отфильтруем множество возможных вариантов, в которых, как мы знаем, есть решение.

largestDivisible :: Integer

largestDivisible = head (filter p [100000,99999..])

  where p x = x `mod` 3829 == 0

Для начала мы создали список всех чисел меньших 100 000 в порядке убывания. Затем отфильтровали список с помощью предиката. Поскольку числа отсортированы в убывающем порядке, наибольшее из них, удовлетворяющее предикату, будет первым элементом отфильтрованного списка. Нам даже не нужно использовать конечный список для нашего базового множества. Снова «лень в действии»! Поскольку мы используем только «голову» списка, нам неважно, конечен полученный список или бесконечен. Вычисления прекращаются, как только находится первое подходящее решение.

Теперь мы собираемся найти сумму всех нечётных квадратов меньших 10 000. Но для начала познакомимся с функцией takeWhile: она пригодится в нашем решении. Она принимает предикат и список, а затем начинает обход списка с его «головы», возвращая те его элементы, которые удовлетворяют предикату. Как только найден элемент, не удовлетворяющий предикату, обход останавливается. Если бы мы хотели получить первое слово строки "слоны умеют веселиться", мы могли бы сделать такой вызов: takeWhile (/=' ') "слоны умеют веселиться", и функция вернула бы "слоны".

Итак, в первую очередь начнём применять функцию (^2) к бесконечному списку [1..]. Затем отфильтруем список, чтобы в нём были только нечётные элементы. Далее возьмём из него значения, меньшие 10000. И, наконец, получим сумму элементов этого списка. Нам даже не нужно задавать для этого функцию – достаточно будет одной строки в GHCi:

ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

166650

Потрясающе! Мы начали с некоторых начальных данных (бесконечный список натуральных чисел) и затем применяли к ним функцию, фильтровали, прореживали до тех пор, пока список не удовлетворил нашим запросам, а затем просуммировали его. Можно было бы воспользоваться генераторами списков для той же цели:

ghci> sum (takeWhile (<10000) [m | m <– [n^2 | n <– [1..]], odd m])

166650

В следующей задаче мы будем иметь дело с рядами Коллатца. Берём натуральное число. Если это число чётное, делим его на два. Если нечётное – умножаем его на 3 и прибавляем единицу. Берём получившееся значение и снова повторяем всю процедуру, получаем новое число, и т. д. В сущности, у нас получается цепочка чисел. С какого бы значения мы ни начали, цепочка заканчивается на единице. Если бы начальным значением было 13, мы бы получили такую последовательность: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Всё по вышеприведённой схеме: 13 × 3 + 1 равняется 40; 40, разделённое на 2, равно 20, и т. д. Как мы видим, цепочка имеет 10 элементов.

Теперь требуется выяснить: если взять все стартовые числа от 1 до 100, как много цепочек имеют длину больше 15? Для начала напишем функцию, которая создаёт цепочку:

chain :: Integer -> [Integer]

chain 1 = [1]

chain n

    | even n = n:chain (n `div` 2)

    | odd n  = n:chain (n*3 + 1)

Так как цепочка заканчивается на единице, это базовый случай. Получилась довольно-таки стандартная рекурсивная функция.

ghci> chain 10

[10,5,16,8,4,2,1]

ghci> chain 1

[1]

ghci> chain 30

[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]

Так! Вроде бы работает правильно. Ну а теперь функция, которая ответит на наш вопрос:

numLongChains :: Int

numLongChains = length (filter isLong (map chain [1..100]))

  where isLong xs = length xs > 15

Мы применяем функцию chain к списку [1..100], чтобы получить список цепочек; цепочки также являются списками. Затем фильтруем их с помощью предиката, который проверяет длину цепочки. После фильтрации смотрим, как много цепочек осталось в результирующем списке.

ПРИМЕЧАНИЕ. Эта функция имеет тип numLongChains :: Int , потому что length возвращает значение типа Int вместо экземпляра класса Num – так уж сложилось исторически. Если мы хотим вернуть более общий тип, имеющий экземпляр класса Num , нам надо применить функцию fromIntegral к результату, возвращённому функцией length .

 

Функция map для функций нескольких переменных

Используя функцию map, можно проделывать, например, такие штуки: map (*) [0..] – если не для какой-либо практической цели, то хотя бы для того, чтобы продемонстрировать, как работает каррирование, и показать, что функции (частично применённые) – это настоящие значения, которые можно передавать в другие функции или помещать в списки (но нельзя представлять в виде строк). До сих пор мы применяли к спискам только функции с одним параметром, вроде map (*2) [0..], чтобы получить список типа (Num a) => [a], но с тем же успехом можем использовать (*) [0..] безо всяких проблем. При этом числа в списке будут применены к функции *, тип которой (Num a) => a –> a –> a. Применение только одного параметра к функции двух параметров возвращает функцию одного параметра. Применив оператор * к списку [0..], мы получаем список функций, которые принимают только один параметр, а именно (Num a) => [a –> a]. Список, возвращаемый выражением map (*) [0..], также можно получить, записав [(0*),(1*),(2*),(3*),(4*),(5*)…

ghci> let listOfFuns = map (*) [0..]

ghci> (listOfFuns !! 4) 5

20

Элемент с номером четыре из списка содержит функцию, которая выполняет умножение на четыре – (4*). Затем мы применяем значение 5 к этой функции. Это то же самое, что записать (4*) 5 или просто 4 * 5.

 

Когда мы разбирались с рекурсией, то во всех функциях для работы со списками наблюдали одну и ту же картину. Базовым случаем, как правило, был пустой список. Мы пользовались образцом (x:xs) и затем делали что-либо с «головой» и «хвостом» списка. Как выясняется, это очень распространённый шаблон. Были придуманы несколько полезных функций для его инкапсуляции. Такие функции называются свёртками (folds). Свёртки позволяют свести структуру данных (например, список) к одному значению.

Функция свёртки принимает бинарную функцию, начальное значение (мне нравится называть его «аккумулятором») и список. Бинарная функция принимает два параметра. Она вызывается с аккумулятором и первым (или последним) элементом из списка и вычисляет новое значение аккумулятора. Затем функция вызывается снова, с новым значением аккумулятора и следующим элементом из списка, и т. д. То, что остаётся в качестве значения аккумулятора после прохода по всему списку, и есть результат свёртки.

 

Левая свёртка foldl

Для начала рассмотрим функцию foldl – свёртка слева. Она сворачивает список, начиная с левой стороны. Бинарная функция применяется для начального значения и первого элемента списка, затем для вновь вычисленного аккумулятора и второго элемента списка и т. д.

Снова реализуем функцию sum, но на этот раз будем пользоваться свёрткой вместо явной рекурсии.

sum' :: (Num a) => [a] –> a

sum' xs = foldl (\acc x –> acc + x) 0 xs

Проверка – раз, два, три!

ghci> sum' [3,5,2,1]

11

Давайте посмотрим более внимательно, как работает функция foldl. Бинарная функция – это лямбда-выражение (\acc x –> acc + x), нуль – стартовое значение, и xs – список. В самом начале нуль используется как значение аккумулятора, а 3 – как значение образца x (текущий элемент). Выражение (0+3) в результате даёт 3; это становится новым значением аккумулятора. Далее, 3 используется как значение аккумулятора и 5 – как текущий элемент; новым значением аккумулятора становится 8. На следующем шаге 8 – значение аккумулятора, 2 – текущий элемент, новое значение аккумулятора становится равным 10. На последнем шаге 10 из аккумулятора и 1 как текущий элемент дают 11. Поздравляю – вы только что выполнили свёртку списка!

Диаграмма на предыдущей странице иллюстрирует работу свёртки шаг за шагом, день за днём. Цифры слева от знака + представляют собой значения аккумулятора. Как вы можете видеть, аккумулятор будто бы «поедает» список, начиная с левой стороны. Ням-ням-ням! Если мы примем во внимание, что функции каррированы, то можем записать определение функции ещё более лаконично:

sum' :: (Num a) => [a] –> a

sum' = foldl (+) 0

Анонимная функция (\acc x –> acc + x) – это то же самое, что и оператор (+). Мы можем пропустить xs в параметрах, потому что вызов foldl (+) 0 вернёт функцию, которая принимает список. В общем, если у вас есть функция вида foo a = bar b a, вы всегда можете переписать её как foo = bar b, так как происходит каррирование.

Ну что ж, давайте реализуем ещё одну функцию с левой свёрткой перед тем, как перейти к правой. Уверен, все вы знаете, что функция elem проверяет, является ли некоторое значение частью списка, так что я не буду этого повторять (тьфу ты – не хотел, а повторил!). Итак:

elem' :: (Eq a) => a –> [a] –> Bool

elem' y ys = foldl (\acc x –> if x == y then True else acc) False ys

Что мы имеем? Стартовое значение и аккумулятор – булевские значения. Тип аккумулятора и стартового значения в свёртках всегда совпадают. Запомните это правило: оно может подсказать вам, что следует использовать в качестве стартового значения, если вы затрудняетесь. В данном случае мы начинаем со значения False. В этом есть смысл: предполагается, что в списке нет искомого элемента. Если мы вызовем функцию свёртки с пустым списком, то результатом будет стартовое значение. Затем мы проверяем текущий элемент на равенство искомому. Если это он – устанавливаем в True. Если нет – не изменяем аккумулятор. Если он прежде был равен значению False, то остаётся равным False, так как текущий элемент – не искомый. Если же был равен True, мы опять-таки оставляем его неизменным.

 

Правая свёртка foldr

Правая свёртка, foldr, работает аналогично левой, только аккумулятор поглощает значения, начиная справа. Бинарная функция левой свёртки принимает аккумулятор как первый параметр, а текущее значение – как второй (\acc x –> …); бинарная функция правой свёртки принимает текущее значение как первый параметр и аккумулятор – как второй (\x acc –> …). То, что аккумулятор находится с правой стороны, в некотором смысле логично, поскольку он поглощает значения из списка справа.

Значение аккумулятора (и, следовательно, результат) функции foldr могут быть любого типа. Это может быть число, булевское значение или даже список. Мы реализуем функцию map с помощью правой свёртки. Аккумулятор будет списком; будем накапливать пересчитанные элементы один за другим. Очевидно, что начальным элементом является пустой список:

map' :: (a –> b) –> [a] –> [b]

map' f xs = foldr (\x acc –> f x : acc) [] xs

Если мы применяем функцию (+3) к списку [1,2,3], то обрабатываем список справа. Мы берём последний элемент, тройку, применяем к нему функцию, и результат оказывается равен 6. Затем добавляем это число к аккумулятору, который был равен []. 6:[] – то же, что и [6]; это новое значение аккумулятора. Мы применяем функцию (+3) к значению 2, получаем 5 и при помощи конструктора списка : добавляем его к аккумулятору, который становится равен [5,6]. Применяем функцию (+3) к значению 1, добавляем результат к аккумулятору и получаем финальное значение [4,5,6].

Конечно, можно было бы реализовать эту функцию и при помощи левой свёртки:

map' :: (a -> b) -> [a] -> [b]

map' f xs = foldl (\acc x –> acc ++ [f x]) [] xs

Но операция конкатенации ++ значительно дороже, чем конструктор списка :, так что мы обычно используем правую свёртку, когда строим списки из списков.

Если вы обратите список задом наперёд, то сможете выполнять правую свёртку с тем же результатом, что даёт левая свёртка, и наоборот. В некоторых случаях обращать список не требуется. Функцию sum можно реализовать как с помощью левой, так и с помощью правой свёртки. Единственное серьёзное отличие: правые свёртки работают на бесконечных списках, а левые – нет! Оно и понятно: если вы берёте бесконечный список в некоторой точке и затем сворачиваете его справа, рано или поздно вы достигаете начала списка. Если же вы берёте бесконечный список в некоторой точке и пытаетесь свернуть его слева, вы никогда не достигнете конца!

Свёртки могут быть использованы для реализации любой функции, где вы вычисляете что-либо за один обход списка. Если вам нужно обойти список для того, чтобы что-либо вычислить, скорее всего, вам нужна свёртка. Вот почему свёртки, наряду с функциями map и filter, – одни из наиболее часто используемых функций в функциональном программировании.

 

Функции foldl1 и foldr1

Функции foldl1 и foldr1 работают примерно так же, как и функции foldl и foldr, только нет необходимости явно задавать стартовое значение. Они предполагают, что первый (или последний) элемент списка является стартовым элементом, и затем начинают свёртку со следующим элементом. Принимая это во внимание, функцию maximum можно реализовать следующим образом:

maximum' :: (Ord a) => [a] -> a

maximum' = foldl1 max

Мы реализовали функцию maximum, используя foldl1. Вместо использования начального значения функция foldl1 предполагает, что таковым является первый элемент списка, после чего перемещается к следующему. Поэтому всё, что ей необходимо, – это бинарная функция и сворачиваемый лист! Мы начинаем с «головы» списка и сравниваем каждый элемент с аккумулятором. Если элемент больше аккумулятора, мы сохраняем его в качестве нового значения аккумулятора; в противном случае сохраняем старое. Мы передаём функцию max в качестве параметра foldl1, поскольку она ровно это и делает: берёт два значения и возвращает большее. К моменту завершения свёртки останется самый большой элемент.

По скольку эти функции требуют, чтобы сворачиваемые списки имели хотя бы один элемент, то, если вызвать их с пустым списком, произойдёт ошибка времени выполнения.

С другой стороны, функции foldl и foldr хорошо работают с пустыми списками. Подумайте, имеет ли смысл свёртка для пустых списков в вашем контексте. Если функция не имеет смысла для пустого списка, то, возможно, вы захотите использовать функции foldl1 или foldr1 для её реализации.

 

Примеры свёрток

Для того чтобы показать, насколько мощны свёртки, мы собираемся реализовать с их помощью несколько стандартных библиотечных функций. Во-первых, реализуем свою версию функции reverse:

reverse' :: [a] -> [a]

reverse' = foldl (\acc x -> x : acc) []

Здесь мы обращаем список, пользуясь пустым списком как начальным значением аккумулятора, и, обходя затем исходный список слева, добавляем текущий элемент в начало аккумулятора.

Функция \acc x -> x : acc – почти то же, что и операция :, за исключением порядка следования параметров. Поэтому функцию reverse' можно переписать и так:

reverse' :: [a] -> [a]

reverse' = foldl (flip (:)) []

Теперь реализуем функцию product:

product' :: (Num a) => [a] -> a

product' = foldl (*) 1

Чтобы вычислить произведение всех элементов списка, следует начать с аккумулятора равного 1. Затем мы выполняем свёртку функцией (*), которая перемножает каждый элемент списка на аккумулятор.

Вот реализация функции filter:

filter' :: (a -> Bool) -> [a] -> [a]

filter' p = foldr (\x acc -> if p x then x : acc else acc) []

Здесь начальное значение аккумулятора является пустым списком. Мы сворачиваем список справа налево и проверяем каждый элемент, пользуясь предикатом p. Если p x возвращает истину, элемент x помещается в начало аккумулятора. В противном случае аккумулятор остаётся без изменения.

Напоследок реализуем функцию last:

last' :: [a] -> a

last' = foldl1 (\ x -> x)

Для получения последнего элемента списка мы применяем foldr1. Начинаем с «головы» списка, а затем применяем бинарную функцию, которая игнорирует аккумулятор и устанавливает текущий элемент списка как новое значение аккумулятора. Как только мы достигаем конца списка, аккумулятор — то есть последний элемент – возвращается в качестве результата свёртки.

 

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

Есть ещё один способ представить работу правой и левой свёртки. Скажем, мы выполняем правую свёртку с бинарной функцией 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].

 

Свёртка бесконечных списков

Взгляд на свёртки как на последовательное применение функции к элементам списка помогает понять, почему правая свёртка иногда отлично работает с бесконечными списками. Давайте реализуем функцию 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.

 

В математике композиция функций определяется следующим образом:

(f ° g)(x) = f (g (x))

Это значит, что композиция двух функций создаёт новую функцию, которая, когда её вызывают, скажем, с параметром x, эквивалентна вызову g с параметром x, а затем вызову f с результатом первого вызова в качестве своего параметра.

В языке Haskell композиция функций понимается точно так же. Мы создаём её при помощи оператора (.), который определён следующим образом:

(.) :: (b –> c) –> (a –> b) –> a –> c

f . g = \x –> f (g x)

По декларации типа функция f должна принимать параметр того же типа, что и результат функции g. Таким образом, результирующая функция принимает параметр того же типа, что и функция g, и возвращает значение того же типа, что и функция f. Выражение negate . (* 3) возвращает функцию, которая принимает число, умножает его на три и меняет его знак на противоположный.

Одно из применений композиции функций – это создание функций «на лету» для передачи их другим функциям в качестве параметров. Конечно, мы можем использовать для этого анонимные функции, но зачастую композиция функций понятнее и лаконичнее. Допустим, что у нас есть список чисел и мы хотим сделать их отрицательными. Один из способов сделать это – получить абсолютное значение числа (модуль), а затем перевести его в отрицательное, вот так:

ghci> map (\x –> negate (abs x)) [5,–3,–6,7,–3,2,–19,24]

[–5,–3,–6,–7,–3,–2,–19,–24]

Обратите внимание на анонимную функцию и на то, как она похожа на результирующую композицию функций. А вот что выйдет, если мы воспользуемся композицией:

ghci> map (negate . abs) [5,–3,–6,7,–3,2,–19,24]

[–5,–3,–6,–7,–3,–2,–19,–24]

Невероятно! Композиция функций правоассоциативна, поэтому у нас есть возможность включать в неё много функций за один раз. Выражение f (g (z x)) эквивалентно (f . g . z) x. Учитывая это, мы можем превратить

ghci> map (\xs –> negate (sum (tail xs))) [[1..5],[3..6],[1..7]]

[–14,–15,–27]

в

ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]]

[–14,–15,–27]

Функция negate . sum . tail принимает список, применяет к нему функцию tail, суммирует результат и умножает полученное число на -1. Получаем точный эквивалент анонимной функции из предыдущего примера.

 

Композиция функций с несколькими параметрами

Ну а как насчёт функций, которые принимают несколько параметров? Если мы хотим использовать их в композиции, обычно мы частично применяем их до тех пор, пока не получим функцию, принимающую только один параметр. Запись

sum (replicate 5 (max 6.7 8.9))

может быть преобразована так:

(sum . replicate 5) (max 6.7 8.9)

или так:

sum . replicate 5 $ max 6.7 8.9

Функция replicate 5 применяется к результату вычисления max 6.7 8.9, после чего элементы полученного списка суммируются. Обратите внимание, что функция replicate частично применена так, чтобы у неё остался только один параметр, так что теперь результат max 6.7 8.9 передаётся на вход replicate 5; новым результатом оказывается список чисел, который потом передаётся функции sum.

Если вы хотите переписать выражение с кучей скобок, используя функциональную композицию, можно сначала записать самую внутреннюю функцию с её параметрами, затем поставить перед ней знак $, а после этого пристраивать вызовы всех других функций, записывая их без последнего параметра и разделяя точками. Например, выражение

replicate 2 (product (map (*3) (zipWith max [1,2] [4,5])))

можно переписать так:

replicate 2 . product . map (*3) $ zipWith max [1,2] [4,5]

Как из одного выражения получилось другое? Ну, во-первых, мы посмотрели на самую правую функцию и её параметры как раз перед группой закрывающихся скобок. Это функция zipWith max [1,2] [4,5]. Так её и запишем:

zipWith max [1,2] [4,5]

Затем смотрим на функцию, которая применяется к zipWith max [1,2] [4,5], это map (*3). Поэтому мы ставим между ней и тем, что было раньше, знак $:

map (*3) $ zipWith max [1,2] [4,5]

Теперь начинаются композиции. Проверяем, какая функция применяется ко всему этому, и присоединяем её к map (*3):

product . map (*3) $ zipWith max [1,2] [4,5]

Наконец, дописываем функцию replicate 2 и получаем окончательное выражение:

replicate 2 . product . map (*3) $ zipWith max [1,2] [4,5]

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

 

Бесточечная нотация

Композиция функций часто используется и для так называемого бесточечного стиля записи функций. Возьмём, для примера, функцию, которую мы написали ранее:

sum' :: (Num a) => [a] –> a

sum' xs = foldl (+) 0 xs

Образец xs представлен дважды с правой стороны. Из–за каррирования мы можем пропустить образец xs с обеих сторон, так как foldl (+) 0 создаёт функцию, которая принимает на вход список. Если мы запишем эту функцию как sum' = foldl (+) 0, такая запись будет называться бесточечной. А как записать следующее выражение в бесточечном стиле?

fn x = ceiling (negate (tan (cos (max 50 x))))

Мы не можем просто избавиться от образца x с обеих правых сторон выражения. Образец x в теле функции заключён в скобки. Выражение cos (max 50) не будет иметь никакого смысла. Вы не можете взять косинус от функции! Всё, что мы можем сделать, – это выразить функцию fn в виде композиции функций.

fn = ceiling . negate . tan . cos . max 50

Отлично! Во многих случаях бесточечная запись легче читается и более лаконична; она заставляет думать о функциях, о том, как их соединение порождает результат, а не о данных и способе их передачи. Можно взять простые функции и использовать композицию как «клей» для создания более сложных. Однако во многих случаях написание функций в бесточечном стиле может делать код менее «читабельным», особенно если функция слишком сложна. Вот почему я не рекомендую создавать длинные цепочки функций, хотя меня частенько обвиняли в пристрастии к композиции. Предпочитаемый стиль – использование выражения let для присвоения меток промежуточным результатам или разбиение проблемы на подпроблемы и их совмещение таким образом, чтобы функции имели смысл для того, кто будет их читать, а не представляли собой огромную цепочку композиций.

Ранее в этой главе мы решали задачу, в которой требовалось найти сумму всех нечётных квадратов меньших 10 000. Вот как будет выглядеть решение, если мы поместим его в функцию:

oddSquareSum :: Integer

oddSquareSum = sum (takeWhile (<10000) (filter odd (map ( 2) [1..])))

Со знанием композиции функций этот код можно переписать так:

oddSquareSum :: Integer

oddSquareSum = sum . takeWhile (<10000) . filter odd $ map ( 2) [1..]

Всё это на первый взгляд может показаться странным, но вы быстро привыкнете. В подобных записях меньше визуального «шума», поскольку мы убрали все скобки. При чтении такого кода можно сразу сказать, что filter odd применяется к результату map ( 2) [1..], что затем применяется takeWhile (<10000), а функция sum суммирует всё, что получилось в результате.