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

Крис Окасаки

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

Москва, 2016

Purely Functional Data Structures

Chris Okasaki
Columbia University

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

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

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

Москва, 2016

УДК
004.432.42

ББК
32.973.2-018
О49

О49
Крис Окасаки
Чисто функциональные структуры данных / Пер. с англ.
– М.: ДМК Пресс, 2016. — 252 с.: ил.
ISBN 978-5-97060-233-1

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

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

УДК 004.432.42

ББК 32.973.2-018

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

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

ISBN 978-0-5216635-0-2 (англ.)
c⃝ Cambridge University Press, 1998

ISBN 978-5-97060-233-1 (рус.)

c⃝ Г. К. Бронников, перевод, 2015
c⃝ Оформление, ДМК Пресс, 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)). Обычно эти вопросы рассматриваются во втором курсе для
студентов, изучающих информатику.
Благодарности. Моё понимание функциональных структур данных
чрезвычайно обогатилось в результате дискуссий со многими специалистами на протяжении многих лет. Мне бы особенно хотелось поблагодарить
Питера Ли, Генри Бейкера, Герта Бродала, Боба Харпера, Хаима Каплана,
Грэма Мосса, Саймона Пейтона Джонса и Боба Тарьяна.

1. Введение

Когда программисту на C для решения определённой задачи требуется эффективная структура данных, он или она обычно могут просто
найти подходящее решение в одном из многих учебников или справочников. К сожалению, для программистов на функциональных языках вроде
Стандартного ML или Haskell такая роскошь недоступна. Хотя большинство справочников стараются быть независимы от языка, независимость
эта получается только в смысле Генри Форда: программисты свободны
выбрать любой язык, если язык этот императивный1. Чтобы несколько
исправить этот дисбаланс, в этой книге я рассматриваю структуры данных с функциональной точки зрения. В примерах программ я использую
Стандартный ML, однако эти программы нетрудно перевести на другие
функциональные языки, например, Haskell или Lisp. Версии наших программ на Haskell можно найти в Приложении A.

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

Методологические преимущества функциональных языков хорошо известны [Bac78, Hug89, HJ94], но тем не менее большинство программ попрежнему пишутся на императивных языках вроде C. Кажущееся противоречие легко объяснить тем, что исторически функциональные языки проигрывали в скорости своим более традиционным аналогам, однако
этот разрыв сейчас сужается. По широкому фронту задач был достигнут
впечатляющий прогресс, начиная от базовой техники построения компиляторов и заканчивая глубоким анализом и оптимизацией программ. Однако одну особенность функционального программирования не исправить
никакими ухищрениями со стороны авторов компиляторов — использование слабых или несоответствующих задаче структур данных. К сожалению, имеющаяся литература содержит относительно мало рецептов помощи в этой области.
Почему оказывается, что функциональные структуры данных труднее спроектировать и реализовать, чем императивные? Здесь две основные

1Генри Форд однажды сказал о цветах автомобилей Модели T: «[Покупатели] могут
выбрать любой цвет, при условии, что он чёрный».

1. Введение

проблемы. Во-первых, с точки зрения проектирования и реализации эффективных структур данных, запрет функционального программирования
на деструктивное обновление (то есть присваивание) является существенным препятствием, подобно запрету для повара использовать ножи. Как и
ножи, деструктивные обновления при неправильном употреблении опасны,
но, будучи пущены в дело должным образом, чрезвычайно эффективны.
Императивные структуры данных часто существенным образом полагаются на присваивание, так что в функциональных программах приходится
искать другие подходы.
Второе затруднение состоит в том, что от функциональных структур
ожидается большая гибкость, чем от их императивных аналогов. В частности, когда мы производим обновление императивной структуры данных,
мы, как правило, принимаем как данность, что старая версия данных более
недоступна, в то время как при обновлении функциональной структуры мы
ожидаем, что как старая, так и новая версия доступны для дальнейшей
обработки. Структура данных, поддерживающая несколько версий, называется устойчивой (persistent), в то время как структура данных, позволяющая иметь лишь одну версию в каждый момент времени, называется эфемерной (ephemeral) [DSST89]. Функциональные языки программирования
обладают тем интересным свойством, что все структуры данных в них автоматически устойчивы. Императивные структуры данных, как правило,
эфемерны. В тех случаях, когда требуется устойчивая структура, императивные программисты не удивляются, что она получается более сложной и,
возможно, даже асимптотически менее эффективной, чем эквивалентная
эфемерная структура.
Более того, теоретики установили нижние границы, которые показывают, что в некоторых ситуациях функциональные языки по своей природе
менее эффективны, чем императивные [BAG92, Pip96]. В свете перечисленного, функциональные структуры данных иногда кажутся похожими
на танцующего медведя, о котором говорится: «поразительна не красота
его танца, а то, что он вообще танцует!» Однако на практике ситуация совсем не так безнадёжна. Как мы увидим, часто оказывается возможным
построить функциональные структуры данных, асимптотически столь же
эффективные, как лучшие императивные решения.

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

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

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

предпочтительнее — тема, обсуждаемая функциональными программистами подчас с религиозным жаром. Различие между двумя порядками вычисления наиболее ярко проявляется в подходах к вычислению аргументов функции. В энергичных языках аргументы вычисляются прежде тела
функции. В ленивых языках вычисление аргументов управляется потребностью; изначально они передаются в функцию в невычисленном виде,
и вычисляются только тогда, когда (и если!) их значение нужно для продолжения работы. Кроме того, после однократного вычисления значение
аргумента кэшируется, так что если оно потребуется снова, его можно получить из памяти, а не перевычислять заново. Такое кэширование называется мемоизация (memoization) [Mic68].
Каждый из этих порядков имеет свои достоинства и недостатки, но
энергичное вычисление явно удобнее по крайней мере в одном отношении: с ним проще рассуждать об асимптотической сложности вычислений.
В энергичных языках то, какие именно подвыражения будут вычислены
и когда, ясно по большей части уже из синтаксиса. Таким образом, рассуждения о времени выполнения каждой данной программы относительно
просты. В то же время в ленивых языках даже эксперты часто испытывают сложности при ответе на вопрос, когда будет вычислено данное подвыражение и будет ли вычислено вообще. Программисты на таких языках
часто вынуждены притворяться, что язык на самом деле энергичен, чтобы
получить хотя бы грубые оценки времени работы.
Оба порядка вычисления влияют на проектирование и анализ структур данных. Как мы увидим, энергичные языки могут описать структуры
с жёсткой оценкой времени выполнения в худшем случае, но не с амортизированной оценкой, а в ленивых языках описываются амортизированные
структуры данных, но не рассчитанные на худший случай. Чтобы описывать обе разновидности структур, требуется язык, поддерживающий оба
порядка вычислений. Мы получаем такой язык, расширяя Стандартный
ML примитивами для ленивого вычисления, как описано в главе 4.

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

Любой разговор о структурах данных содержит опасность возникновения путаницы, поскольку у термина структура данных (data structure)
есть по крайней мере четыре различных связанных между собой значения.

• Абстрактный тип данных (то есть тип и набор функций над этим
типом). Для этого значения мы будем пользоваться словом абстракция (abstraction).