Читать фрагмент

книга

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

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

Форматы: PDF

Издательство: ДМК Пресс

Год: 2023

Место издания: Москва

ISBN: 978-5-89818-577-0

Страниц: 252

Артикул: 108010

Возрастная маркировка: 16+

Электронная книга

499 ₽

Купить и скачать

Содержание

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

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

Предисловие

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. Конечные отображения

Литература

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

Внимание!
При обнаружении неточностей или ошибок в описании книги "Чисто функциональные структуры данных (автор Крис Окасаки)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!