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

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

От редактора перевода
Предисловие
1. Введение
1.1. Функциональные и императивные структуры данных
1.2. Энергичное и ленивое вычисление
1.3. Терминология
1.4. Наш подход
1.5. Обзор книги
2. Устойчивость
2.1. Списки
2.2. Двоичные деревья поиска
2.3. Примечания
3. Знакомые структуры данных в функциональном окружении
3.1. Левоориентированные кучи
3.2. Биномиальные кучи
3.3. Красно-чёрные деревья
3.4. Примечания
4. Ленивое вычисление
4.1. $-запись
4.2. Потоки
4.3. Примечания
5. Основы амортизации
5.1. Методы амортизированного анализа
5.2. Очереди
5.3. Биномиальные кучи
5.4. Расширяющиеся кучи
5.5. Парные кучи
5.6. Плохие новости
5.7. Примечания
6. Амортизация и устойчивость при ленивом вычислении
6.1. Трассировка вычисления и логическое время
6.2. Сочетание амортизации и устойчивости
6.2.1. Роль ленивого вычисления
6.2.2. Общая методика анализа ленивых структур данных
6.3. Метод банкира
6.3.1. Обоснование метода банкира
6.3.2. Пример: очереди
6.3.3. Наследование долга
6.4. Метод физика
6.4.1. Пример: биномиальные кучи
6.4.2. Пример: очереди
6.4.3. Сортировка слиянием снизу вверх с совместным использованием
6.5. Ленивые парные кучи
6.6. Примечания
7. Избавление от амортизации
7.1. Расписания
7.2. Очереди реального времени
7.3. Биномиальные кучи
7.4. Сортировка снизу вверх с расписанием
7.5. Примечания
8. Ленивая перестройка
8.1. Порционная перестройка
8.2. Глобальная перестройка
8.2.1. Пример: очереди реального времени по Худу–Мелвиллу
8.3. Ленивая перестройка
8.4. Двусторонние очереди
8.4.1. Деки с ограниченным выходом
8.4.2. Деки по методу банкира
8.4.3. Деки реального времени
8.5. Примечания
9. Числовые представления
9.1. Позиционные системы счисления
9.2. Двоичные числа
9.2.1. Двоичные списки с произвольным доступом
9.2.2. Безнулевые представления
9.2.3. Ленивые представления
9.2.4. Сегментированные представления
9.3. Скошенные двоичные числа
9.3.1. Скошенные двоичные списки с произвольным доступом
9.3.2. Скошенные биномиальные кучи
9.4. Троичные и четверичные числа
9.5. Примечания
10. Развёртка структур данных
10.1. Структурная декомпозиция
10.1.1. Гетерогенная рекурсия и Стандартный ML
10.1.2. Снова двоичные списки с произвольным доступом
10.1.3. Развёрнутые очереди
10.2. Структурная абстракция
10.2.1. Списки с эффективной конкатенацией
10.2.2. Кучи с эффективным слиянием
10.3. Развёртка до составных типов
10.3.1. Префиксные деревья
10.3.2. Обобщённые префиксные деревья
10.4. Примечания
11. Неявное рекурсивное замедление
11.1. Очереди и деки
11.2. Двусторонние очереди с конкатенацией
11.3. Примечания
A. Код на языке Haskell
A.1. Очереди
A.2. Двусторонние очереди
A.3. Списки с конкатенацией
A.4. Двусторонние очереди с конкатенацией
A.5. Списки с произвольным доступом
A.6. Кучи
A.7. Сортируемые коллекции
A.8. Множества
A.9. Конечные отображения
Литература
Предметный указатель