Жемчужины проектирования алгоритмов: функциональный подход. С примерами на языке Haskell

Ричард Бёрд

Жемчужины проектирования

алгоритмов: функциональный подход

Pearls of Functional Algorithm
Design

Richard Bird
University of Oxford

Жемчужины проектирования
алгоритмов: функциональный
подход

С примерами на языке Haskell

Ричард Бёрд
Оксфордский университет

Перевод с английского
В. Н. Брагилевского и А. М. Пеленицына

Москва, 2023

2-е издание, электронное

УДК 004.021+004.421
ББК 32.973-018
Б11

Б11
Бёрд, Ричард.
Жемчужины проектирования алгоритмов: функциональный подход. 
С примерами на языке Haskell / Р. Бёрд ; пер. с англ. В. Н. Брагилевско-
го, А. М. Пеленицына. — 2-е изд., эл. — 1 файл pdf : 331 с. — Москва : 
ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe 
Digital Editions 4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-555-8

В этой книге Ричард Бёрд представляет принципиально новый подход к проектированию 
алгоритмов, а именно проектирование посредством формального вывода. 
Основное содержание книги разделено на 30 коротких глав, называемых жемчужинами, 
в каждой из которых решается конкретная программистская задача. 
Эти задачи, некоторые из них абсолютно новые, происходят из таких разнообразных 
источников, как игры и головоломки, захватывающие комбинаторные построения 
и более традиционные алгоритмы сжатия данных и сопоставления строк.
Каждая жемчужина начинается с постановки задачи, формулируемой на функциональном 
языке программирования Haskell, чрезвычайно мощном и в то же 
время лаконичном, позволяющем легко и просто выражать алгоритмические идеи. 
Новшество книги состоит в том, что каждое решение формально вычисляется из 
исходной постановки задачи посредством обращения к законам функционального 
программирования.
Издание предназначено для программистов, увлекающихся функциональным 
программированием, студентов, аспирантов и преподавателей, интересующихся 
принципами проектирования алгоритмов, а также всех, кто желает приобрести и 
развить навыки рассуждений в эквациональном стиле применительно к программам 
и алгоритмам.

УДК 004.021+004.421 
ББК 32.973-018

Электронное издание на основе печатного издания: Жемчужины проектирования 
алгоритмов: функциональный подход. С примерами на языке Haskell / Р. Бёрд ; пер. с англ. 
В. Н. Брагилевского, А. М. Пеленицына. — Москва : ДМК Пресс, 2015. — 330 с. — ISBN 
978-5-97060-161-7. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских 
прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-555-8
© Cambridge University Press
©  Перевод на русский язык, оформление, 
ДМК Пресс, 2015

Посвящается моей жене Норме.

Оглавление

Предисловие
9

1
Наименьшее отсутствующее число
12

2
Превосходная задача
19

3
Улучшаем седловой поиск
24

4
Задача о выборке
35

5
Сортировка попарных сумм
42

6
Делаем сотню
49

7
Строим дерево минимальной высоты
58

8
Распутываем жадные алгоритмы
68

9
Поиск знаменитостей
75

10 Удаляем повторы
84

11 Вовсе не максимальная сумма сегмента
94

12 Ранжируем суффиксы
101

13 Преобразование Барроуза–Уилера
115

14 Последний хвост
128

15 Все общие префиксы
139

Жемчужины проектирования алгоритмов: функциональный подход

16 Алгоритм Бойера—Мура
145

17 Алгоритм Кнута—Морриса—Пратта
156

18 Планирование в «Час пик»
166

19 Простой алгоритм решения судоку
178

20 Задача «Обратного отсчёта»
189

21 Хиломорфизмы и нексусы
202

22 Три способа вычисления определителей
215

23 Внутри выпуклой оболочки
224

24 Рациональное арифметическое кодирование
236

25 Целочисленное арифметическое кодирование
247

26 Алгоритм Шора—Вейта
262

27 Упорядоченная вставка
274

28 Бесцикловые функциональные алгоритмы
287

29 Алгоритм Джонсона—Троттера
298

30 Прядение паутины для чайников
306

Предметный указатель
326

Предисловие

В 1990 году, когда журнал Journal of Functional Programming (JFP)
только планировался к выходу, бывшие тогда редакторами Саймон Пей-
тон Джонс (Simon Peyton Jones) и Филипп Вадлер (Philip Wadler) попросили 
меня взяться за постоянную колонку под названием Функциональные 
жемчужины (Functional Pearls). Их идея заключалась в подражании
чрезвычайно успешной серии эссе Джона Бентли (Jon Bentley) «Жемчужины 
программирования», которые публиковались в 80-е годы в журнале
Communications of the ACM. Вот что Бентли писал о своих жемчужинах:

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

Мне кажется, что редакторы обратились именно ко мне, потому что я
интересовался следующим подходом: я брал понятную, но неэффективную
функциональную программу, выступавшую в роли спецификации к решаемой 
задаче, а затем посредством эквациональных рассуждений приходил
к более эффективной версии. Одним из факторов, стимулирующих рост
интереса к функциональным языкам в 90-е годы, было именно удобство
применения эквациональных рассуждений. В самом деле, акроним в названии 
функционального языка GOFER, изобретённого Марком Джонсом
(Mark Jones), отражает как раз эту идею. GOFER стал одним из языков,
повлиявших на развитие языка Haskell, на котором основывается настоящая 
книга. Эквациональные рассуждения доминируют здесь над всем.

Жемчужины проектирования алгоритмов: функциональный подход

За последние 20 лет в JFP и изредка на таких конференциях как
International Conference of Functional Programming (ICFP) и Mathematics
of Program Construction Conference (MPC) появилось около 80 жемчужин.
Из них я написал примерно четверть, большая же часть написана другими. 
Темы этих жемчужин включают интересные выводы программ, новые
структуры данных, а также маленькие, но элегантные встроенные в Haskell
и ML предметно-ориентированные языки для конкретных приложений.
Мне всегда были интересны алгоритмы и их проектирование. Отсюда
название этой книги — Жемчужины проектирования алгоритмов: функциональный 
подход — вместо более общего Функциональные жемчужины. 
Многие, хотя и не все, жемчужины начинаются со спецификации на
языке Haskell, а затем продолжаются выводом более эффективной реализации. 
При написании конкретно этих жемчужин мне хотелось выяснить,
до какой степени проектирование алгоритма можно представить в виде
традиционного в математике вычисления результата посредством применения 
общеизвестных принципов, теорем и законов. Хотя в математике
вычисления обычно производятся для упрощения сложных выражений, в
проектировании алгоритмов получается в точности наоборот: простые, но
неэффективные программы преобразуются в более эффективные, но, возможно, 
неочевидные. Жемчужиной является не полученная в итоге программа, 
а скорее процесс её получения. Остальные жемчужины, в части
из них совсем немного преобразований, посвящены попыткам дать простые
объяснения некоторым интересным и довольно хитроумным алгоритмам.
Объяснение идей, лежащих в основе алгоритма, при функциональном подходе 
оказывается гораздо проще, чем при императивном: составляющие
алгоритм функции легче отделить, они коротки и отражают мощные вычислительные 
шаблоны.
Жемчужины в этой книге, появлявшиеся прежде в JFP и других местах, 
были неоднократно отшлифованы. Собственно, многие не слишком
сильно напоминают оригиналы. Даже при этом их несложно отшлифовать
ещё лучше. Золотым стандартом красоты в математике считается книга
Айгнера (Aigner) и Циглера (Ziegler) Proofs from The Book (третье издание,
Springer, 2003), содержащая совершенные доказательства математических
теорем. Я всегда рассматриваю эту книгу как идеал, к которому следует
стремиться.
Примерно треть жемчужин новые. С некоторыми явно обозначенными 
исключениями жемчужины можно читать в любом порядке, хотя главы
были упорядочены до некоторой степени по темам, таким как «разделяй
и властвуй», жадные алгоритмы, полный перебор и т.п. В жемчужинах
присутствует небольшое повторение материала, по большей части отно-

Оглавление
11

сящегося к свойствам используемых библиотечных функций или к более
общим законам, таким как законы слияния для разнообразных свёрток.
При необходимости читатель может обратиться к добавленному к книге
короткому предметному указателю.
Наконец, в этой книге собраны идеи многих людей. Некоторые жемчужины 
были изначально написаны в сотрудничестве с другими авторами. 
Я хотел бы поблагодарить Шэрон Кёртис (Sharon Curtis), Джереми
Гиббонса (Jeremy Gibbons), Ральфа Хинзе (Ralf Hinze), Герэйнта Джонса
(Geraint Jones) и Шин-Чень Му (Shin-Cheng Mu), моих соавторов, за щедрое 
разрешение переработать этот материал. Джереми Гиббонс прочитал
окончательную версию черновика и сделал множество полезных предложений, 
направленных на улучшение изложения. Некоторые жемчужины
досконально обсуждались на встречах исследовательской группы Algebra
of Programming в Оксфорде. Хотя многие из недостатков и ошибок были
исправлены, нет никаких сомнений в том, что при этом добавились новые.
Помимо упомянутых ранее, я хотел бы выразить благодарность Стивену
Дрейпу (Stephen Drape), Тому Харперу (Tom Harper), Дэниэлю Джеймсу
(Daniel James), Джеффри Лейку (Jeffrey Lake), Менг Вонг (Meng Wang) и
Николасу Ву (Nicholas Wu) за предложения по улучшению текста. Я также 
хотел бы поблагодарить Ламберта Мертенса (Lambert Meertens) и Уга
де Мура (Oege de Moor) за плодотворное многолетнее сотрудничество. Наконец, 
я в долгу у Дэвида Транаха (David Tranah), моего редактора в
издательстве Cambridge University Press, за содействие и поддержку, и в
том числе за столь необходимые технические советы по подготовке окончательной 
версии.

Ричард Бёрд

Наименьшее отсутствующее число

Введение

Рассмотрим задачу отыскания наименьшего натурального числа, отсутствующего 
в заданном конечном множестве натуральных чисел 𝑋.
Здесь мы имеем дело с упрощённой версией более общей программистской 
задачи, в которой числа соответствуют некоторым объектам, а 𝑋 —
множество объектов, используемых в настоящий момент. Задача заключается 
в том, чтобы найти некоторый неиспользуемый объект, например, с
наименьшим именем.
Разумеется, решение задачи зависит от способа представления множества 
𝑋. Если 𝑋 задано списком без повторений, где элементы упорядочены
в порядке возрастания, то решение очевидно: в последовательности элементов 
следует искать первый пропуск. Предположим, однако, что множество
𝑋 задано списком различных чисел в произвольном порядке, например:

[08, 23, 09, 00, 12, 11, 01, 10, 13, 07, 41, 04, 14, 21, 05, 17, 03, 19]

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