Почему функциональное программирование не исследовало динамические деревья?

19

Динамические деревья играют важную роль в решении таких проблем, как сетевые потоки, динамические графы, комбинаторные задачи («Динамические деревья на практике» Тарьяна и Вернека) и недавно объединенные словари («Простой объединяемый словарь» Адама Карчмара),

Под динамическими деревьями я ссылаюсь на определение, изложенное в статье Слеатора и Тарьяна «Структура данных для динамических деревьев» в 1983 году. С тех пор в области исследований функционального программирования было опубликовано мало усилий.

  1. Эдвард Кметт реализовал версию деревьев ST в основном как перевод аналога C ++, см. Деревья с разрезом ссылок .
  2. Крис Окасаки написал ограниченную реализацию деревьев Splay в своей известной книге «Чисто функциональные структуры данных».
  3. Ральф Хинце и Росс Патерсон представили функциональную структуру данных, называемую деревьями 2-3 пальца, но с целью, несколько отличной от первоначального определения динамических деревьев

Реализация (и, возможно, производительность) динамических деревьев делятся в соответствии с тремя подходами:

  1. Линеаризация, где инопланетные деревья (тур Эйлера) играют большую роль. Не найдено чисто функциональное исследование.
  2. Разложение пути, где деревья ST являются флагманами, только что нашло версию Kmett.
  3. Сжатие деревьев, где топ-деревья, топологические деревья и RC-деревья являются игроками. Не найдено чисто функциональное исследование.

Чисто функциональный анализ и реализацию можно найти на Splay, AVL, красно-чёрном дереве, но это НЕ динамические деревья. Первые считаются теневой (также называемой виртуальной или вспомогательной) структурой данных последних.

Итак, мой вопрос:

По каким причинам (недостаткам, слабым сторонам) исследовательское сообщество по функциональному программированию не принимает участия в структуре данных динамических деревьев?

data-structures trees functional-programming Ричард Чемберс
источник
14
Я не понимаю, как на это можно ответить без формирования авторитетного комитета сообщества по функциональному программированию для формирования официальных мнений. Разве мы не можем переформулировать вопрос так, чтобы здесь можно было что-то ответить? Насколько я могу судить, ОП должен просто пойти и реализовать свои динамические деревья в Хаскеле или что-то еще, а затем вернуться сюда, чтобы сообщить, что это было сделано в конце концов.
Андрей Бауэр
Обновление до @AndrejBauer: ОП ушел и внедрил свои динамические деревья в Haskell: arxiv.org/abs/1908.11105
jbapple

Ответы:

-1

«В информатике функциональное программирование - это парадигма программирования. Стиль построения структуры и элементов компьютерных программ, который рассматривает вычисления как оценку математических функций и избегает изменения состояния и изменчивых данных». - Википедия

«изменяющееся состояние и изменяемые данные», другими словами, «динамический».

Так что ваш вопрос немного похож на вопрос, почему левый не прав.

Энтони Бахлер
источник
1
Функциональные программы могут представлять динамические данные с постоянными структурами данных. Этот вопрос задает вопрос, почему разработка постоянных структур данных для определенной проблемы не была исследована. Вопрос имеет смысл.
Восстановить Монику