Функции высших порядков

В результате изучения материала главы 3 студент должен:

знать

• • понятия функций высшего порядка, область их применения в функциональных программах;
• • понятия лямбда-выражений и методы их использования в функциях высших порядков;
• • то, в каких случаях можно использовать естественный параллелизм в определении функций;

уметь

• • пользоваться стандартными функциями высших порядков для массовой обработки данных;
• • применять стандартные функции обработки списков для получения коротких и понятных программ;

владеть

• • навыками применения функций высших порядков в программировании на языке Haskell;
• • навыками избавления от рекурсии при обработке сложных структур данных.

Отображение и свертка. Лямбда-выражения

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

Мы, однако, начнем не с описания функции суперпозиции, а с других примеров, в которых функции используются в качестве аргументов других функций. В первую очередь рассмотрим стандартную функцию обработки списков тар, которая, получив в качестве аргументов список и функцию преобразования элементов этого списка, выдает в качестве результата список из преобразованных элементов, полученных применением функционального параметра к каждому элементу списка. Если, например, функция sqr возводит свой аргумент в квадрат, то с помощью функции тар можно, имея список целых чисел, получить список их квадратов: map sqr [1, 2, 5, -2] -" [1, 4, 25, 4].

Функция тар — это стандартная функция, определенная в ядре языка. Однако по уже сложившейся традиции приведем ее описание заново. Прежде всего, определим ее тип. Первым аргументом нашей функции является функция, которая здесь имеет один целый аргумент и возвращает целый результат. Тип этого первого аргумента будет (Integer -> Integer). Второй аргумент и результат функции — это списки целых типа [Integer]. Таким образом, тип функции тар будет выглядеть как map: (Integer -> Integer) -> [Integer] -> [Integer].

В действительности не столь важно, что исходный и результирующий списки содержат именно элементы типа Integer. Фактически исходные элементы могут иметь произвольный тип а. Тогда, если функция, являющаяся первым аргументом функции тар, имеет тип (а -> Ь), то результирующий список будет содержать элементы типа Ь. Теперь мы готовы описать полностью функцию тар, включая и ее тип (листинг 3.1).

Листинг 3.1. Определение функции отображения списков — шар

тар:: (а -> Ь) -> [а] -> [Ь].

— результат применения тар к пустому списку — пустой список тар _ [] = [].

тар func (x:s) = (func х): (тар func s).

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

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

Из нашего описания очевидно, что вычисление результата применения функции к первому элементу списка не зависит от того, как вычисляется отображение остальной части списка. Фактически, если в системе имеется достаточное количество вычислительных ресурсов, то вычисление результатов применения функции к элементам списка можно производить параллельно. Хотя общее время работы функции тар пропорционально длине списка аргумента (считая, что время обработки каждого элемента списка одно и то же), в вычислениях на многопроцессорных машинах или в распределенном кластере функция тар работает чрезвычайно эффективно.

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

Пусть требуется составить список всех простых сомножителей заданного большого списка натуральных чисел. Можно для решения составить рекурсивную функцию, имеющую один дополнительный накапливающий аргумент — упорядоченный список уже найденных простых сомножителей. Кроме того, напишем простую функцию, вычисляющую наименьший простой множитель натурального числа, большего единицы. Для простоты не будем сильно заботиться об эффективности этой последней функции. Например, функция может быть написана следующим образом. minFactor n = minFactor' п 2.

where minFactor' n d I n 'mod⁴ d == 0 = d.

I otherwise = minFactor' n (d+1).

Теперь функция обработки списка натуральных чисел может выглядеть так (первый аргумент — исходный список, второй — генерируемый список простых сомножителей): factorList [] factors = factors.

factorList (l:xs) factors = factorList xs factors factorList (x:xs) factors =.

factorList ((x 'div⁴ d):xs) (insert d factors) where d = minFactor x.

insert d [] = [d].

insert d factors® (f: fs) | d < f = d: factors.

| d == f = factors | otherwise = f: insert d fs.

На простых примерах можно убедиться в том, что функция работает правильно. Например, написав выражение factorList [12, 24, 36, 25] [ ], мы получим правильный ответ [2,3,5]. Наша функция последовательно обрабатывает элементы исходного списка, получая, но очереди простые сомножители каждого числа. Однако можно значительно ускорить работу, если вычислять простые сомножители каждого элемента списка параллельно с другими элементами. Этого можно достичь с помощью функции тар.

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

Полный текст программы с некоторыми комментариями содержится в листинге 3.2.

Листинг 3.2. Программа вычисления списка простых сомножителей списка чисел.

• — Функция factors выдает упорядоченный список простых
• — сомножителей заданного натурального числа

factors: Integer -> [Integer].

factors n = reverse $ factors' n 2 [] where

— Вспомогательная функция factors' имеет два накапливающих — аргумента — очередной проверяемый делитель d и — уже вычисленный список простых сомножителей, меньших d.

factors' 1 _ list = factors' n d list.

list.

| d * d > n = add n list.

| n 'mod' d == 0 = factors' (n 'div' d) d (add d list).

| otherwise = factors' n (d+1) list — Функция add добавляет очередной сомножитель в начало — списка, так что окончательный список оказывается — перевернутым, add d [ ] = [d].

add d listQ (xixs) | d == x = list.

| otherwise = d: list.

• — Функция merge сливает без повторений два упорядоченных
• — списка целых в один

merge:: Ord, а => [а] -> [а] -> [а].

merge [] list = list.

merge list [] = list.

merge listl®(xl:xsl) list20(x2:xs2).

| xl < x2 = xl: merge xsl list2 | xl == x2 = xl: merge xsl xs2 | otherwise = x2: merge listl xs2.

— Функция mergeLists сливает без повторений список — упорядоченных списков в один список. mergeLists:: Ord, а => [ [а] ] -> [а].

mergeLists [] = [].

mergeLists (list:lists) = merge list $ mergeLists lists.

— Основная функция для решения задачи получения списка всех — простых делителей заданного списка натуральных чисел. factorList: [Integer] -> [Integer] factorList list = mergeLists $ map factors list.

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

В простейшем случае, когда функция может быть определена с помощью только одного уравнения, лямбда-выражение имеет такой же вид, как и это единственное уравнение. Разница состоит в том, что в левой его части вместо имени функции стоит символ обратной косой черты (изображающий греческую букву «лямбда» — А,), а вместо знака равенства для отделения образцов для аргументов от правой части уравнения используется последовательность символов ' ->¹. Например, если функция sqr для возведения числа в квадрат не определена, то мы можем написать лямбда-выражение для ее определения непосредственно там, где эта функция используется.

Тогда вызов функции шар для получения списка квадратов, упомянутый в начале главы, будет выглядеть следующим образом: тар (х -> х * х) [1, 2, 5, -2].

Если уравнений несколько, то их можно объединить в одно выражение с помощью условного выражения if либо специальной конструкции для выбора по образцам — case. Например, для того чтобы получить список из знаков заданного списка целых чисел с помощью функции тар (знак числа — это функция, выдающая ноль, единицу или минус единицу в зависимости от того, является ли число нулевым, положительным или отрицательным), можно поступить следующими способами. Во-первых, определить отдельно функцию для вычисления знака числа, скажем, таким образом:

signum 0=0.

signum n | n < 0 = -1.

| otherwise = 1.

Тогда вызов для нахождения списка знаков заданного списка чисел выглядел бы как map signum [2,5,0,-3,2,-2].

(в результате получится список [1, 1, 0, -1, 1, -1]).

Второй способ вызова, при котором функция вычисления знака числа определяется прямо в точке вызова, будет выглядеть так (вместо трех уравнений использовано условное выражение):

map (-> if п == 0 then 0 else if n < 0 then -1 else 1).

[2,5/0,-3,2,-2].

Наконец, определение функции лямбда-выражением с использованием конструкции case будет выглядеть следующим образом: map (-> case n of

0 -> 0.

п | п -1.

| otherwise -> 1) [2,5,0,-3,2,-2].

Конструкция case позволяет произвести выбор среди нескольких образцов точно так же, как это происходит при вызове функции с некоторым аргументом. В данном случае роль такого аргумента играет выражение, стоящее непосредственно после ключевого слова case. Мы не будем углубляться в тонкости синтаксиса для всестороннего изучения конструкции case, тем более что она нам в дальнейшем почти не понадобится. Однако заметим, что привычное определение именованной функции всегда может быть переформулировано с помощью лямбда-выражения, если только в правых частях уравнений этой функции не используется имя самой функции. Так, приведенное выше определение функции signum на самом деле является лишь другой синтаксической формой для определения с помощью лямбда-выражения: signum = -> case n of

0 -> 0.

п | п -1 | otherwise -> 1.

Приведем еще одну форму записи, в которой именованная функция определяется в выражении локально с помощью лямбда-выражения и блока where. В следующей строчке вычисляются факториалы первых 10.

натуральных чисел:

map factorial [1.10] where

factorial = -> if n == 0 then 1 else n * factorial (n-1).

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

Блок where может содержать и несколько определений функций, мы уже использовали такую запись в листинге 3.2, причем каждая из этих функций может иметь и несколько уравнений, и даже определение типа. Таким образом, локальное определение функций может быть сделано в той же форме, что и глобальное: map factorial [1.10] where

factorial:: Integer -> Integer factorial 0=1.

factorial n | n > 0 = n * factorial (n-1).

Вернемся к функциям высших порядков. Функция тар получает в качестве аргумента функцию одного аргумента и применяет ее к элементам списка, в результате чего получается новый список. Можно рассмотреть еще одну функцию высшего порядка, которая будет «сворачивать» список, вырабатывая на базе всех элементов списка одно значение. Такая функция для соединения отдельных элементов списка в одно значение должна получать бинарную операцию — функцию двух аргументов. Эта бинарная операция будет последовательно применяться к элементам списка так, чтобы в результате обработки всего списка получилось одно значение. Например, если бинарную операцию сложения применять последовательно ко всем элементам списка (в качестве начального значения можно взять ноль), то в результате получится сумма всех элементов списка. Если же в качестве бинарной операции взять операцию умножения, то в результате перемножения всех элементов списка получится произведение этих элементов (теперь в качестве начального значения нужно будет взять единицу).

В стандартной библиотеке языка Haskell имеются две функции высшего порядка, одна из которых применяет заданную бинарную операцию к элементам списка от начала списка к его концу, а вторая начинает обработку элементов с конца списка, применяя заданную в качестве аргумента операцию последовательно, двигаясь по направлению к началу списка. Первая из этих операций называется foldl, вторая — foldr. Общее название для этих операций — операции свертки списка. Конечно, если применяемая к элементам списка бинарная операция ассоциативна (как сложение или умножение), то порядок обработки элементов — с начала или конца списка — не важен.

Приведем определения функций свертки списка. В этих определениях (листинг 3.3) f — применяемая бинарная операция (или функция с двумя аргументами), seed — начальное значение (оно будет результатом работы функции свертки, если обрабатываемый список не содержит ни одного элемента).

Листинг 3.3. Определение функций свертки списков — f oldl и f oldr

foldl:: (b -> a -> b) -> b -> [a] -> b.

foldl _ seed [] = seed.

foldl f seed (x:s) = foldl f (f seed x) s.

foldr:: (a -> b -> b) -> b -> [a] -> b.

foldr _ seed [] = seed.

foldr f seed (x:s) = f x (foldr f seed s).

Рассмотрим уравнения, определяющие эти функции подробнее (ограничимся только функцией foldr, уравнения для функции foldl аналогичны). Как и в случае функции тар, первое уравнение определяет поведение функции свертки для случая, когда исходный список пуст. Как мы уже говорили, в этом случае результатом должно быть начальное значение, определяемое аргументом seed. Если же исходный список не пуст, то, прежде всего, построим свертку хвоста списка с помощью рекурсивного обращения к функции foldr, а затем применим нашу бинарную операцию f к первому элементу списка и результату свертки хвоста. В результате получится искомый результат.

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

Сумму всех элементов заданного списка list теперь можно получить простым вызовом любой из функций foldl или foldr при условии, что в качестве начального значения выбирается ноль, а в качестве бинарной операции берется операция сложения: foldl (+) 0 list.

однако функция свертки — это довольно мощная функция, которая может применяться в самых разных, порой довольно неожиданных ситуациях. Например, если описать операцию присоединения элемента к началу списка в виде операции addElem addElem list elem = elemrlist.

(заметим, что эта операция отличается от стандартного конструктора списков (:) только порядком аргументов), то функция «переворачивания» списка, которую мы описывали в гл. 1 в виде функции reverse, теперь может быть выражена с помощью применения функции foldl: reverse list = foldl addElem [] list.

В этой версии функции обращения списка нет явной рекурсии. Рекурсивные вызовы «спрятаны» внутри функции foldl. Функции высших порядков часто позволяют писать короткие и выразительные программы, не содержащие в явном виде рекурсии. Ниже приведена версия функции вычисления факториала, в которой для вычисления сначала строится список целых чисел от единицы до заданного значения аргумента, а потом все элементы полученного списка перемножаются для получения результата:

factorial n = foldr (*) 1 [l.n].

В отличие от функции тар свертка списка производится последовательно, так как бинарной операции необходимы значения обоих аргументов для того, чтобы вычислить результат. Впрочем, если в качестве начального значения берется один из элементов списка, то в случае ассоциативной операции можно было бы производить свертку отдельных участков списка независимо от других и затем соединять результаты операций. В библиотеке Haskell наряду с функциями foldl и f oldr существуют их варианты foldll и foldrl, которые не требуют начального значения, а в качестве такого начального значения берут первый или, соответственно, последний элементы самого списка. Разумеется, эти функции неприменимы к пустому списку. Если бинарная операция, применяемая для свертки, ассоциативна, то эти функции могли бы обрабатывать различные участки списка параллельно, повышая тем самым производительность в случае многопроцессорных систем.

К сожалению, ассоциативность — это свойство, которое трудно распознать аналитически. Например, суммирование элементов непустого списка [3, 7, 2, 4, 10] можно провести с помощью выражения foldll (+) [3, 7, 2, 4, 10].

в результате чего получится значение 26, а с помощью похожего выражения.

foldll (-) [3, 7, 2, 4, 10].

получится значение 3 — 7 — 2 — 4 — 10 = -20. Но если первое значение можно получить, применяя сложение в любом порядке, например, (3 + 7) + (2 + 4) + 10, и, значит, обработку списка можно было бы провести параллельно, то во втором случае аналогичное построение (3−7) — (2−4) — 10 даст совсем не тот результат.

Попробуем написать функцию, которая для ассоциативной бинарной операции f даст тот же результат, что и свертки foldll и foldrl, но пытается запустить бинарную операцию параллельно на двух участках списка. Подобная функция даст нам преимущество перед обычной сверткой в случае очень «тяжелой» бинарной операции при работе в многопроцессорных системах:

fold2:: (а -> а -> а) -> [а] -> а.

fold2 _ [х] = х.

fold2 f [х, у] = f х у.

fold2 f (xl:x2:xs) = f (f xl x2) (fold2 f xs).

Попробуем применить нашу новую свертку к списку [3, 7, 2, 4,

10], используя операцию сложения в качестве бинарной операции: fold2 (+) [3, 7, 2, 4, 10]:

" fold2 (+) [3, 7, 2, 4, 10].

Попытка удачна, но посмотрим на последовательность редукций, которая получается в случае применения обычной свертки foldll и нашей свертки fold2. Обычная свертка дает следующую последовательность выражений:

foldll (+) [3, 7, 2, 4, 10].

• 3 + foldll (+) [ 7, 2, 4, 10]
• 3 + (7 + foldll (+) [2, 4, 10])
• 3 + (7 + (2 + foldll (+) [4, 10]))
• 3 + (7 + (2 + (4 + foldll (+) [10])))
• 3 + (7 + (2 + (4 + 10)))
• 3 + (7 + (2 + 14))
• 3 + (7 + 16)
• 3 + 23 26

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

fold2 (+) [3, 7, 2, 4, 10].

• (3 + 7) + f old2 (+) [ 2, 4, 10]
• (3 + 7) + ((2 + 4) + fold2 (+) [10])
• (3 + 7) + ((2 + 4) + 10)
• 10 + (6 + 10)
• 10 + 16 26

Некоторая экономия достигнута — мы смогли вычислить «параллельно» суммы (3 + 7) и (2 + 4). Однако на этом наш параллелизм заканчивается. Функция fold2 позволяет выполнить параллельно операции над парами элементов, но в дальнейшем обработка все равно происходит строго последовательно. Можно ли «распространить» параллелизм дальше?

Рассмотрим еще одну версию свертки — функцию f old3:

fold3:: (а -> а -> а) -> [а] -> а.

fold3 _ [х] = х.

fold3 f [х, у] = f х у.

fold3 f list = f (fold3 f first) (fold3 f second) where (first, second) = splitAt (length list 'div' 2) list.

Чтобы увидеть эффект от параллелизма, продемонстрируем работу этой функции па чуть более длинном списке из восьми элементов. При этом будем «параллельно» вычислять те значения, которые на каждом этапе уже готовы для вычисления: fold3 (+) [1, 2, 3, 4, 5, 6, 7, 8].

fold3 (+) [1, 2, 3, 4] + fold3 (+) [5, 6, 7, 8].

• (fold3 (+) [1, 2] + fold3 (+) [3, 4]) +
• (f old3 (+) [5, 6] + f old3 (+) [7, 8])
• ((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8))
• (3 + 7) + (11 + 15)
• 10 + 26 36

Теперь с параллелизмом все в порядке, проблема только в том, что функция splitAt для очень длинных списков будет работать неэффективно. Вместо линейной по длине списка функции мы получили квадратичную. Кроме того, что splitAt работает не за константное время, она еще и порождает новые списки во время своей работы, так что эффективность по объему требуемой памяти тоже не очень высока. Впрочем, все эти недостатки могут быть перевешены выгодой от параллелизма, если действительно наша операция «сложения» элементов существенно более сложная, так что имеет смысл выполнять ее в максимально возможном параллелизме.

Позже, в гл. 8 мы вернемся к вопросу о параллелизме при выполнении свертки с помощью ассоциативной бинарной операции.

Функции высших порядков, выдающие функции в качестве результата, можно определять, чтобы строить новые функции на основе других. Наверное, одной из самых распространенных операций над функциями является их суперпозиция (или композиция). Такая операция позволяет по двум функциям fug получить новую функцию f g такую, что результат ее применения к аргументу f g х будет тем же, что и результат последовательного применения функций f и g: f (д х). В отличие от традиционных языков программирования, в которых описать подобную функцию, как правило, невозможно, в языке Haskell такое описание не составляет никакого труда:

comp:: (b -> а) -> (с -> Ь) -> (с -> а) comp f g = х -> f (g x).

Такая функция имеется в стандартной библиотеке языка Haskell в виде бинарной операции (.) • Это означает, что если имеется функция возведения числового значения в квадрат sqr, то функция возведения числа в четвертую степень power4 может быть получена с помощью вызова.

power4 = sqr. sqr.

В дальнейшем мы будем использовать операцию композиции довольно часто.

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

flip:: (а -> b -> с) -> (Ь -> а -> с) flip func = х у -> func у х Теперь функцию обращения списка можно определить, не используя явного описания вспомогательной функции addElem: reverse list = foldl (flip (:)) [] list.

Заметим, что описанный алгоритм обращения списка работает очень эффективно и обращает список за линейное время. Ранее такого результата мы добивались, используя преобразование функций с помощью введения дополнительных аргументов. Обратите внимание еще и на то, что функции flip передается аргументом конструктор списков (:), который в данном случае использован в качестве бинарной операции. Это как раз тот случай, когда конструктор используется в роли обычной функции.

Вспомним функцию сортировки списка методом простых вставок, приведенную в листинге 2.16. В этой программе мы определили две функции — simpleSort и insert. Первая рекурсивная функция осуществляла сортировку списка с помощью вставки элементов в упорядоченный список, и эту вставку как раз и обеспечивала функция insert. В том примере мы обсуждали, как заставить рекурсивную функцию быть более эффективной посредством концевой рекурсии и накапливающих аргументов. Теперь напишем функцию simpleSort вовсе без рекурсии: simpleSort list = foldl insert [] list.

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