Обработка списков с помощью функций высших порядков

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

Фильтрация списка позволяет отобрать в списке те элементы, которые удовлетворяют некоторому заданному условию (предикату). Разумеется, условие — это функция, которая принимает в качестве аргумента элемент списка и выдает логическое значение. Если выданное значение — True, то элемент остается в списке, если False — удаляется. Функцию фильтрации несложно написать и самому, приведенный ниже код дает ясное представление о том, что именно делает функция: filter:: (а -> Bool) -> [а] -> [а].

filter _[] = [].

filter condition (x:xs) | condition x = x: filtered.

| otherwise = filtered where filtered = filter xs.

Если условие фильтрации condition — это сложная функция, то фактически работа фильтрации тоже может быть распараллелена, и приведенная выше реализация подчеркивает этот факт: проверка условия condition х может быть запущена параллельно с вычислением фильтра оставшихся после отбрасывания х элементов (filtered).

Если требуется не просто отбросить элементы, не удовлетворяющие условию, а собрать их в отдельный список, то пригодится похожая функция partition, которая, правда, в отличие от filter определена только в модуле Data. List. Его нужно подключить к вашему модулю с помощью конструкции import, если вы планируете воспользоваться данной функцией. Приведенные ниже строки показывают, что получается в результате применения функции partition к списку, хотя на самом деле ее реализация чуть более сложна, чем это показано ниже, и не содержит двух обращений к функции фильтрации. Обратите внимание на то, как сделано обращение условия во втором применении функции filter — это просто композиция заданного условия condition и функции логического отрицания not:

partition:: (а -> Bool) -> [а] -> ([а], [а]).

partition condition list =.

(filter condition list, filter (not. condition) list).

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

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

quicksort (x:xs) = quicksort first ++ [x] ++ quicksort second.

where (first, second) = partition (e -> e < x) xs.

Конечно, в пакете Data. List существует и своя реализация функции сортировки списка — функция sort, по работа с ней довольно сложна и не сводится к нашей простой quicksort. Стоит заметить, что эффективность нашей реализации не очень высока, и не столько потому, что этот алгоритм вообще не очень хорошо работает в некоторых случаях, сколько из-за частого применения операции (++) соединения списков. Впрочем, несложно провести оптимизацию этой функции, просто добавив накапливающий аргумент. Оптимизированный вариант выглядит не так красиво, но работает быстрее и может действительно показывать производительность порядка 0(N log JV), как это и бывает при использовании алгоритма быстрой сортировки:

quicksort list = quicksort' list [] where quicksort' [] list = list quicksort' (x:xs) list =.

quicksort' first (x: quicksort' second list) where (first, second) = partition (e -> e < x) xs.

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

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

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

[" aeiouy", «bcdfghjklmnpqrstvwxz», «12 345 678 9», «(),.;:?!-» ].

Символы, не входящие ни в одну строку, будут иметь нулевой класс, гласные буквы — класс 1, согласные — класс 2 и т. д. Требуется по заданному тексту собрать статистику: сколько символов текста относятся к тому или иному классу классу. Например, по тексту «Haskell» будет собрана статистика [1,2,4,0,0], т. е. в тексте имеется один символ, не относящийся ни к какому классу (эго заглавная ' Н¹), две гласные буквы, четыре согласные, цифры и знаки препинания в тексте отсутствуют.

Будем считать, что таблица классов символов определена в программе в виде константы classTable типа [String]. Напишем, прежде всего, функцию, которая по заданному символу будет определять его класс. Аргументами функции будут символ и таблица классов символов: getClass: Char -> [ [Char]] -> Int.

getClass c [] = 0.

getClass c (s:rest) | c 'elerrT s = 1.

I restClass ==0=0.

I otherwise = restClass + 1 where restClass = getClass c rest В этой функции использована стандартная операция elem, которая проверяет, является ли некоторое значение элементом списка. В данном случае она используется для того, чтобы проверить, к какому классу относится символ.

Теперь можно приступить к обработке текста. Первым шагом обработки будет вычисление класса для каждого символа текста. Этот шаг реализуется функцией processl, которая с помощью функции отображения шар, возможно, параллельно обрабатывает каждый символ текста: processl: String -> [Int].

processl text = map (c -> getClass c classTable) text.

На следующем шаге подготовим полученный список классов для суммирования. Для этого превратим каждый номер класса в шкалу из нулей и единиц, в которой единица будет стоять на месте, соответствующем номеру класса, а остальные элементы шкалы станут нулями. Этот шаг будет реализован функцией process2, в которой также используется определенный ниже список номеров классов allClasses: allClasses: [Int].

allClasses = [0.length classTable].

process2: [Int] -> [[Int]].

process2 classes = map flags classes where

flags n = map (i -> if i == n then 1 else 0) allClasses Теперь для сбора полной статистики останется выполнить свертку полученного списка шкал, складывая элементы этих шкал почленно. Для почленного сложения списков определим операцию (+++). Позже мы увидим, что для такой операции можно использовать гораздо более общую стандартную функцию, однако пока напишем свою рекурсивную операцию почленного сложения:

(+++): [Int] -> [Int] -> [Int].

[] +++ [] = [].

(xlrxsl) +++ (x2:xs2) = (xl + x2): (xsl +++ xs2).

Сбор статистики заключается в свертке полученного списка шкал с помощью операции сложения элементарных статистик (+++):

statistics: String -> [Int].

statistics text = foldll (+++) (process2 (processl text)).

Полностью программа сбора статистики по тексту представлена в листинге 3.4.

Листинг 3.4. Сбор статистики символов по заданному тексту

— Таблица классов символов classTable: [ [Char]].

classTable = [" aeiouy", «bcdfghjklmnpqrstvwxz» ,.

" 123 456 789″, «О,.;:?!-» ].

— Функция определения класса символа getClass: Char -> [ [Char]] -> Int.

getClass c [] = 0.

getClass c (s:rest) | c 'elem⁴ s = 1.

I restClass ==0=0.

I otherwise = restClass + 1 where restClass = getClass c rest.

— Список классов allClasses:: [Int].

allClasses = [0.length classTable].

— Первый шаг обработки текста processl: String -> [Int].

processl text = map (c -> getClass c classTable) text.

— Второй шаг обработки текста.

process2: [Int] -> [[Int]].

process2 classes = map flags classes where.

flags n = map (i -> if i == n then 1 else 0) allClasses.

— Почленное сложение элементарных статистик (+++): [Int] -> [Int] -> [Int].

[] + + + [] = [].

• (xl:xsl) +++ (x2:xs2) = (xl + x2): (xsl +++ xs2)
• — Сбор статистики statistics: String -> [Int]

statistics text = foldll (+++) (process2 (processl text)).

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

Рассмотрим еще одну задачу. Пусть требуется по заданной строке получить список содержащихся в ней слов. Словом будем считать любую последовательность рядом стоящих символов, для которых стандартная функция isLetter из модуля Data. Char выдает значение True. Проще всего сначала заменить в тексте все символы, не являющиеся буквами, на пробелы, а потом воспользоваться стандартной функцией words, которая и выполнит за нас всю требуемую работу. Вот как может выглядеть подобная функция: wordsList: String -> [String] wordsList text = words $.

map (c -> if isLetter c then c else ' ') text.

Другое решение может состоять в том, что символы исходного текста собираются в группы по определенному признаку, в данном случае, но тому, является ли символ буквой. В библиотеке Haskell имеется функция group, которая собирает элементы списка в группы равных между собой рядом стоящих элементов. Например, group [2,3,3,2,2,2,4,4,5] выдаст в качестве результата [[2], [3,3], [2,2,2], [4,4], [5]]. Эту функцию можно обобщить: вместо равенства использовать любое отношение эквивалентности, которое будет считать «одинаковыми» два значения, если некоторая функция от этих значений выдает True. Такое обобщение тоже есть — это функция groupBy, имеющая тип groupBy:: (а -> а -> Bool) -> [а] -> [ [а] ].

Теперь можно назвать два символа «равными», если они оба являются буквой:

equalsAsLetter cl с2 = isLetter cl && isLetter c2.

Попробуем применить функцию groupBy к некоторому тексту, использовав в качестве функции «равенства» нашу функцию equalsAsLetter: >> groupBy equalsAsLetter «hello, world!» .

[" hello" ,", «,» «,» world" ," !" ].

Видно, что все слова действительно выделились в группы символов, а остальные символы остались в строчках из одного этого символа. Теперь, чтобы завершить задачу осталось отфильтровать полученный список. Приведем полный текст программы для решения задачи получения списка слов текста (листинг 3.5).

Листинг 3.5. Выделение слов текста.

wordsList:: String -> [String].

wordsList text = filter isWord $ groupBy equalsAsLetter text where equalsAsLetter cl c2 = isLetter cl && isLetter c2 isWord w = isLetter $ head w.

Проверим, как работает наша функция:

" wordsList «I was born in the year 1632, in the city of York.» [" I" ," was" ," born" ," in" ," the" ," year" ," in" ," the" ," city", «of», «York» ] Расмотрим еще пару функций обработки списков: zip и unzip. Первая из них берет два списка и составляет из их элементов список пар соответствующих друг другу элементов. Так, если выполнить команду «zip «hello» «world» то получим в результате.

[('h','w'),(^,e^I,^,o^,),(^,l',^,r'),(^,l^,,^,l^,),(^,o',^,d¹)].

Исходные списки могут иметь разную длину, тогда более длинный список обрезается, его последние элементы игнорируются:

" zip «hello» [1.10].

[ ('h', 1), (' е ', 2) ,('1', 3), Cl', 4), Со', 5) ].

Рассмотрим следующую задачу: требуется найти самое длинное слово в тексте. Мы уже умеем выделять в тексте слова, и если есть список слов, то мы легко можем получить список их длин, применив с помощью шар функцию length к каждому слову. Если мы теперь найдем максимальное значение в списке длин, то определим длину самого длинного слова. Но как найти само это слово? Конечно, можно еще раз просмотреть исходный список в поисках в нем слова с найденной длиной, но есть иной вариант: соединим список слов со списком их длин с помощью «застежки» zip. Теперь можно выбрать «максимальную» пару и уже из нее извлечь требуемое слово. Заметим, что кортежи сравиниваются с помощью операций сравнения, если можно сравнивать их элементы, при этом сравнение происходит в лексикографическом порядке: сначала сравниваются первые элементы кортежей, при их равенстве — вторые, и т. д., пока не определится, какой из кортежей больше, или не окажется, что кортежи равны.

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

Вернемся к задаче поиска самого длинного слова. Искомая функция записывается в одну (правда, довольно длинную) строчку: longestWord: String -> String.

longestWord text = snd $ maximum $ zip (map length words) words where words = wordsList text.

Добавим определение функции longestWord к файлу, который уже содержит определение функции wordsList, загрузим этот файл в интерпретатор и проверим, работает ли наша функция:

" longestWord «I was born in the year 1632, in the city…» «year» .

В этом тексте самое длинное слово имеет четыре буквы, но почему выбрано именно слово «year» из середины текста? Это произошло потому, что пара (4, «year») оказалась наибольшей по величине среди всех пар (4, «born»), (4, «year») и (4, «city»), ведь при равенстве первых элементов кортежа начинают сравниваться вторые, а из слов «born», «year» и «city» последним, но алфавиту (самым большим!) оказалось слово «year» .

Обратной к функции zip является функция unzip, которая из списка пар получает два списка одинаковой длины. Поскольку функция может иметь только один результат, то эти два списка упаковываются в кортеж из двух элементов, так что функция unzip имеет тип unzip: [(а, Ь) ] -> ([а], [Ь]).

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

zipWith:: (а -> b -> с) -> [а] -> [Ь] -> [с].

zip:: [а] -> [Ь] -> [ (а, Ь) ].

zipWith _ [] _ = [].

zipWith _ _ [] = [].

zipWith f (xl:xsl) (x2:xs2) = f xl x2: zipWith f xsl xs2 zip list list2 = zipWith (,) listl list2.

Для поэлементной обработки трех списков имеются функции zip3 и zipWith3, а также unzip3, а если потребуется параллельная обработка сразу четырех или более списков, то можно подключить модуль Data. List, в котором определены аналогичные функции для четырех, пяти, шести и семи списков.

Одним из вариантов соединения функций отображения и свертки являются функции scanl и scanr, которые выполняют пошаговую свертку списка, оставляя на каждом шаге промежуточный результат так, что в результате их работы образуется новый список из промежуточных результатов свертки. Сигнатура этих функций совпадает с сигнатурой функций foldl и foldr с той лишь разницей, что функции fold вырабатывают один конечный результат, а функции scan — целый список:

" :t foldr.

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

>> :t scanr.

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

" foldl (+) 0 [1.5].

>> scanl (+) 0 [1.5].

[0,1,3,6,10,15].

С помощью функций scan можно строить списки, содержащие элементы, которые получаются вычислением на основе предыдущих элементов. Например, составим список факториалов натуральных чисел от 1 до 10:

>> scanl (*) 1 [1.10].

[1,1,2,6,24,120,720,5040,40 320,362880,3 628 800].

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

" let exp х = sum $ scanl (u n -> u*x/fromlnteger n) 1 [1.10].

exp:: Fractional a => a -> a >> exp 1.

2.7 182 818 011 463 845.

Значение числа e получено с точностью до семи десятичных знаков после запятой.

В ходе дальнейшего изложения мы будем использовать описанные и многие другие функции обработки списков, как использующие, так и не использующие функциональные аргументы. Читателям рекомендуется ознакомиться с некоторыми функциями модуля Data. List, описание которых не было приведено в данной главе. Полезными могут оказаться функции соединения списков concat и concatMap, функции поиска элементов в списке elem и notElem, функции проверки свойств элементов списка any и all, функции, работающие со списками как с множествами элементов, — union, intersect, delete и многие другие функции. Конечно, в приводимых примерах смысл тех или иных используемых функций будет объяснен, но для самостоятельного решения задач может оказаться полезным использовать функции, которые еще не встречались в тексте книги.