Этот вопрос вдохновлен другим вопросом о том, что нового в ПФДС с момента публикации книги Окасаки в 1998 году .
Я начну с двух вопросов, которые у меня есть:
- Существует ли чисто функциональная структура данных набора, которая приближается к скорости хеш-таблиц? Попытки еще не там.
- Существуют ли чисто функциональные деревья пальца с добавлением O (1)? На данный момент лучшим является O (LG LG N), разработанный Капланом и Тарьяном.
Какие другие чисто функциональные проблемы структуры данных открыты?
big-list
ds.data-structures
functional-programming
оборота jbapple
источник
источник
Ответы:
Я объясню вопрос несколько либерально. Для структур данных в стиле Окасаки запоминание является формой неявной мутации, которая оказывает побочный эффект на время выполнения. Поэтому я возьму вопрос о постоянных структурах данных в строгом смысле, а не о структурах данных с чисто функциональной реализацией, которые являются подмножеством первых. Под строгим пониманием я подразумеваю, что вы должны иметь возможность получать доступ к более старым версиям структуры данных без штрафа, дерево версий может произвольно ветвиться и т. Д.
В этом контексте я считаю, что постоянный поиск союзов является важной открытой проблемой. Есть бумага Кончона-Филлиата, которая упоминалась в другой ветке. Комментатор уже поднял проблему с их так называемым постоянным массивом: он действительно только полупостоянный. Но предположим, что вы заменили его хеш-кодом или другим действительно постоянным массивом, который ведет себя лучше в худшем (и, возможно, среднем) случае, но хуже в лучшем случае. Это все еще оставляет важный вопрос открытым:
Статья дает формальное доказательство правильности в Coq. Но они не могут справиться с амортизированной сложностью ни формально, ни неформально. Это очень не ясно мне , что сложно за кадром мутация приводит к ожидаемому амортизационной сложности во всех случаях. Когда я в последний раз думал об этом, я был несколько уверен, что смогу создать контрпример, если приложу к этому усилия. Даже если я ошибаюсь в этой последней части, отсутствие надлежащего анализа является серьезным пробелом; Понятно, что классический анализ амортизации UNION-FIND Траяна не переносит напрямую.
источник
Вот один из них:
Что такое чисто функциональный эквивалент слабой хеш-таблицы?
источник