Чисто функциональные структуры данных

Крис Окасаки

Чисто функциональные
структуры данных

Москва, 2023

Purely Functional Data Structures

Chris Okasaki
Columbia University

Чисто функциональные
структуры данных

Крис Окасаки
Колумбийский университет

Перевод с английского Г. К. Бронникова
под редакцией В. Н. Брагилевского

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

Москва, 2023

УДК 004.432.42
ББК 32.973.2-018
О-49

О-49
Окасаки, Крис.

Чисто функциональные структуры данных / К. Окасаки ; пер. с англ. 
Г. К. Бронникова ; под ред. В. Н. Брагилевского. — 2-е изд., эл. — 1 файл 
pdf : 252 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe 
Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный.

ISBN 978-5-89818-577-0

Большинство книг по структурам данных предполагают использование императивного языка программирования, например, C/C++ или Java. Однако реализации структур данных на таких языках далеко не всегда хорошо переносятся на 
функциональные языки программирования, такие как Стандартный ML, Haskell 
или Scheme. В этой книге структуры данных описываются с точки зрения функциональных языков, в ней содержатся примеры и предлагаются подходы к проектированию, которые могут использоваться разработчиками при создании их собственных структур данных. Книга включает в себя как классические структуры 
данных, к примеру, красно-чёрные деревья и биномиальные очереди, так и некоторые новые структуры данных, созданные специально для функциональных языков. Весь исходный код приводится на Стандартном ML и Haskell, причём большинство программ нетрудно адаптировать для других функциональных языков 
программирования.
Это издание представляет собой справочное руководство для профессиональных программистов, работающих с функциональными языками, и может также 
использоваться в качестве учебника для самостоятельного изучения.

УДК 004.432.42 
ББК 32.973.2-018

Электронное издание на основе печатного издания: Чисто функциональные структуры данных / К. Окасаки ; пер. с англ. Г. К. Бронникова ; под ред. В. Н. Брагилевского. — 
Москва : ДМК Пресс, 2016. — 252 с. — ISBN 978-5-97060-233-1. — Текст : непосредственный.

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

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

ISBN 978-5-89818-577-0
© Cambridge University Press, 1998
© Г. К. Бронников, преревод, 2015
© Оформление, ДМК Пресс, 2016

Оглавление

От редактора перевода
8

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

1. Введение
11

1.1. Функциональные и императивные структуры данных . . . .
11

1.2. Энергичное и ленивое вычисление
. . . . . . . . . . . . . . .
12

1.3. Терминология
. . . . . . . . . . . . . . . . . . . . . . . . . . .
13

1.4. Наш подход . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

1.5. Обзор книги . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15

2. Устойчивость
17

2.1. Списки
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17

2.2. Двоичные деревья поиска
. . . . . . . . . . . . . . . . . . . .
21

2.3. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
26

3. Знакомые структуры данных в функциональном окружении
27

3.1. Левоориентированные кучи
. . . . . . . . . . . . . . . . . . .
27

3.2. Биномиальные кучи . . . . . . . . . . . . . . . . . . . . . . . .
31

3.3. Красно-чёрные деревья . . . . . . . . . . . . . . . . . . . . . .
35

3.4. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
40

4. Ленивое вычисление
41

4.1. $-запись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41

4.2. Потоки
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

4.3. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
46

5. Основы амортизации
49

5.1. Методы амортизированного анализа . . . . . . . . . . . . . .
49

5.2. Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52

5.3. Биномиальные кучи . . . . . . . . . . . . . . . . . . . . . . . .
55

5.4. Расширяющиеся кучи . . . . . . . . . . . . . . . . . . . . . . .
57

5.5. Парные кучи . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64

5.6. Плохие новости
. . . . . . . . . . . . . . . . . . . . . . . . . .
66

5.7. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
67

Оглавление

6. Амортизация и устойчивость при ленивом вычислении
69

6.1. Трассировка вычисления и логическое время . . . . . . . . .
69

6.2. Сочетание амортизации и устойчивости . . . . . . . . . . . .
71

6.2.1.
Роль ленивого вычисления . . . . . . . . . . . . . . . .
71

6.2.2.
Общая методика анализа ленивых структур данных .
72

6.3. Метод банкира . . . . . . . . . . . . . . . . . . . . . . . . . . .
74

6.3.1.
Обоснование метода банкира
. . . . . . . . . . . . . .
75

6.3.2.
Пример: очереди . . . . . . . . . . . . . . . . . . . . . .
77

6.3.3.
Наследование долга . . . . . . . . . . . . . . . . . . . .
81

6.4. Метод физика . . . . . . . . . . . . . . . . . . . . . . . . . . .
82

6.4.1.
Пример: биномиальные кучи
. . . . . . . . . . . . . .
84

6.4.2.
Пример: очереди . . . . . . . . . . . . . . . . . . . . . .
86

6.4.3.
Сортировка слиянием снизу вверх с совместным использованием
. . . . . . . . . . . . . . . . . . . . . . .
88

6.5. Ленивые парные кучи . . . . . . . . . . . . . . . . . . . . . . .
94

6.6. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
95

7. Избавление от амортизации
98

7.1. Расписания . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99

7.2. Очереди реального времени . . . . . . . . . . . . . . . . . . .
101

7.3. Биномиальные кучи . . . . . . . . . . . . . . . . . . . . . . . .
105

7.4. Сортировка снизу вверх с расписанием
. . . . . . . . . . . .
110

7.5. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
114

8. Ленивая перестройка
116

8.1. Порционная перестройка . . . . . . . . . . . . . . . . . . . . .
116

8.2. Глобальная перестройка
. . . . . . . . . . . . . . . . . . . . .
118

8.2.1.
Пример: очереди реального времени по Худу–Мелвиллу119

8.3. Ленивая перестройка . . . . . . . . . . . . . . . . . . . . . . .
122

8.4. Двусторонние очереди
. . . . . . . . . . . . . . . . . . . . . .
124

8.4.1.
Деки с ограниченным выходом . . . . . . . . . . . . .
125

8.4.2.
Деки по методу банкира . . . . . . . . . . . . . . . . .
126

8.4.3.
Деки реального времени . . . . . . . . . . . . . . . . .
129

8.5. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
130

9. Числовые представления
133

9.1. Позиционные системы счисления . . . . . . . . . . . . . . . .
134

9.2. Двоичные числа . . . . . . . . . . . . . . . . . . . . . . . . . .
134

9.2.1.
Двоичные списки с произвольным доступом
. . . . .
138

9.2.2.
Безнулевые представления . . . . . . . . . . . . . . . .
142

Оглавление
7

9.2.3.
Ленивые представления
. . . . . . . . . . . . . . . . .
144

9.2.4.
Сегментированные представления
. . . . . . . . . . .
147

9.3. Скошенные двоичные числа . . . . . . . . . . . . . . . . . . .
150

9.3.1.
Скошенные двоичные списки с произвольным доступом152

9.3.2.
Скошенные биномиальные кучи . . . . . . . . . . . . .
155

9.4. Троичные и четверичные числа . . . . . . . . . . . . . . . . .
159

9.5. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
161

10. Развёртка структур данных
162

10.1. Структурная декомпозиция . . . . . . . . . . . . . . . . . . .
163

10.1.1. Гетерогенная рекурсия и Стандартный ML . . . . . .
164

10.1.2. Снова двоичные списки с произвольным доступом . .
165

10.1.3. Развёрнутые очереди . . . . . . . . . . . . . . . . . . .
169

10.2. Структурная абстракция . . . . . . . . . . . . . . . . . . . . .
173

10.2.1. Списки с эффективной конкатенацией . . . . . . . . .
175

10.2.2. Кучи с эффективным слиянием . . . . . . . . . . . . .
181

10.3. Развёртка до составных типов . . . . . . . . . . . . . . . . . .
186

10.3.1. Префиксные деревья . . . . . . . . . . . . . . . . . . .
186

10.3.2. Обобщённые префиксные деревья
. . . . . . . . . . .
190

10.4. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
193

11. Неявное рекурсивное замедление
195

11.1. Очереди и деки
. . . . . . . . . . . . . . . . . . . . . . . . . .
195

11.2. Двусторонние очереди с конкатенацией
. . . . . . . . . . . .
200

11.3. Примечания
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
209

A. Код на языке Haskell
210

A.1. Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
210

A.2. Двусторонние очереди
. . . . . . . . . . . . . . . . . . . . . .
215

A.3. Списки с конкатенацией . . . . . . . . . . . . . . . . . . . . .
216

A.4. Двусторонние очереди с конкатенацией
. . . . . . . . . . . .
217

A.5. Списки с произвольным доступом
. . . . . . . . . . . . . . .
221

A.6. Кучи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
225

A.7. Сортируемые коллекции . . . . . . . . . . . . . . . . . . . . .
232

A.8. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
232

A.9. Конечные отображения . . . . . . . . . . . . . . . . . . . . . .
234

Литература
236

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

От редактора перевода

Книга Криса Окасаки «Чисто функциональные структуры данных»
даже спустя почти 20 лет после публикации остаётся единственным достаточно полным источником информации по разработке и анализу производительности различных структур данных в функциональном окружении.
Разумеется, за прошедшее время было получено множество новых результатов∗, однако работы, которая бы их обобщала, к сожалению, пока не
появилось. Книга сочетает техническую точность в изложении основных
результатов и академическую строгость их обоснования.
Русский перевод этой книги можно считать чрезвычайно удачным
дополнением к выпущенной издательством ДМК Пресс в 2013 году книги Ричарда Бёрда «Жемчужины проектирования алгоритмов: функциональный подход», вместе они обеспечивают читателя богатым арсеналом
средств для разработки эффективных алгоритмов и структур данных при
работе с функциональными языками программирования. Надеемся, что
это издание будет способствовать распространению интереса к функциональному программированию в русскоязычном сообществе.
Перевод книги был выполнен Георгием Бронниковым. Благодарим
также Романа Кашицына, Всеволода Опарина, Кирилла Заборского, Александра Карпича и Дмитрия Косарева за участие в работе по подготовке
настоящего издания.

Виталий Брагилевский,
Институт математики, механики и компьютерных наук
Южного федерального университета, Ростов-на-Дону

∗Подробный их перечень можно найти в ответе на вопрос Евгения Кирпичёва по адресу
http://cstheory.stackexchange.com/q/1539/.

Предисловие

Я впервые познакомился с языком Стандартный ML в 1989 году.
Мне всегда нравилось программировать эффективные реализации структур данных, и я немедленно занялся переводом некоторых своих любимых
программ на Стандартный ML. Для некоторых структур перевод оказался
достаточно простым и, к моему большому удовольствию, получался код
значительно более краткий и ясный, чем предыдущие версии, написанные мной на C, Pascal или Ada. Однако не всегда результат оказывался
столь приятным. Раз за разом мне приходилось использовать разрушающее присваивание, которое в Стандартном ML не приветствуется, а во
многих других функциональных языках вообще запрещено. Я пытался обращаться к литературе, но нашёл лишь несколько разрозненных статей.
Понемногу я стал понимать, что столкнулся с неисследованной областью,
и начал искать новые способы решения задач.
Сейчас, восемь лет спустя, мой поиск продолжается. Всё ещё есть много примеров структур данных, которые я просто не знаю как эффективно
реализовать на функциональном языке. Однако за это время я получил
множество уроков о том, что в функциональных языках работает. Эта
книга является попыткой записать выученные уроки, и я надеюсь, что она
послужит справочником для функциональных программистов, а также как
текст для тех, кто хочет больше узнать о структурах данных в функциональном окружении.
Стандартный ML. Несмотря на то, что структуры данных из этой
книги можно реализовать практически на любом функциональном языке,
я во всех примерах буду использовать Стандартный ML. У этого языка
имеются следующие преимущества для моих целей: (1) энергичный порядок вычислений, что значительно упрощает рассуждения о том, сколько
времени потребует тот или иной алгоритм, и (2) замечательная система модулей, идеально подходящая для выражения абстрактных типов данных.
Однако пользователи других языков, например, Haskell или Lisp, смогут
без труда адаптировать мои примеры к своим вычислительным окружениям. (В приложении я привожу переводы большинства примеров на Haskell.)
Даже программисты на C или Java должны быть способны реализовать
эти структуры данных, хотя в случае C отсутствие автоматической сборки
мусора иногда будет доставлять неприятности.

Предисловие

Читателям, незнакомым со Стандартным ML, я рекомендую в качестве введения книги ML для программиста-практика Полсона [Pau96] или
Элементы программирования на ML Ульмана [Ull94].
Прочие предварительные требования. Эта книга не рассчитана
служить первоначальным общим введением в структуры данных. Я предполагаю, что читателю достаточно знакомы основные абстрактные структуры данных — стеки, очереди, кучи (приоритетные очереди) и конечные
отображения (словари). Кроме того, я предполагаю знакомство с основами анализа алгоритмов, особенно с нотацией «большого O» (например,
O(n log n)). Обычно эти вопросы рассматриваются во втором курсе для
студентов, изучающих информатику.
Благодарности. Моё понимание функциональных структур данных
чрезвычайно обогатилось в результате дискуссий со многими специалистами на протяжении многих лет. Мне бы особенно хотелось поблагодарить
Питера Ли, Генри Бейкера, Герта Бродала, Боба Харпера, Хаима Каплана,
Грэма Мосса, Саймона Пейтона Джонса и Боба Тарьяна.