Чисто функциональная структура данных
-
Определение и преимущества чисто функциональных структур данных
- Чисто функциональные структуры данных неизменяемы и обеспечивают полную сохраняемость, быстрое копирование и потокобезопасность.
- Отложенная оценка и запоминание могут быть использованы для повышения эффективности.
-
Различия между постоянными и непостоянными структурами данных
- Постоянные структуры данных сохраняют свои предыдущие версии, в то время как непостоянные структуры допускают деструктивное обновление.
- Массивы являются примером непостоянных структур данных, которые не являются чисто функциональными.
-
Сравнение с деструктивными обновлениями
- Деструктивные обновления не могут быть отменены, но могут быть эффективными.
- Замена массива картой, списком произвольного доступа или деревом может быть более эффективной, но с увеличением стоимости доступа.
-
Обеспечение чисто функциональной структуры данных
- В нечистых функциональных языках необходимо использовать модули или классы для управления доступом к данным.
-
Примеры чисто функциональных структур данных
- Стек, очередь, двусторонняя очередь, мультимножество, карта, приоритетная очередь и список произвольного доступа являются примерами чисто функциональных структур данных.
-
Методы проектирования и реализации
- Лень и запоминание являются ключевыми инструментами для построения эффективных чисто функциональных структур данных.
- Амортизированный анализ и планирование используются для доказательства эффективности структур данных, даже если они не являются чисто функциональными.
-
Ссылки и дополнительные ресурсы
- Ссылки на внешние ресурсы, включая диссертацию Окасаки и курсы MIT OpenCourseWare.
Полный текст статьи: