Jakie są nierozstrzygnięte pytania dotyczące czysto funkcjonalnych struktur danych?

To pytanie jest inspirowane innym pytaniem o to, co nowego w PFDS od publikacji książki Okasaki w 1998 roku .

Zacznę od dwóch pytań, które mam:

• Czy istnieje czysto funkcjonalna struktura danych, która zbliża się do prędkości tabel mieszania? Prób jeszcze tam nie ma.
• Czy istnieją czysto funkcjonalne drzewa palcowe z dołączonym O (1)? Najlepsze jak dotąd to O (lg lg n), opracowane przez Kaplana i Tarjana.

Jakie inne czysto funkcjonalne problemy ze strukturą danych są otwarte?

Zinterpretuję to pytanie dość swobodnie. W przypadku struktur danych w stylu Okasaki, zapamiętywanie jest formą ukrytej mutacji, która ma wpływ uboczny na czas działania. Dlatego przyjmuję pytanie dotyczące trwałych struktur danych w ścisłym tego słowa znaczeniu, a nie struktur danych z czysto funkcjonalną implementacją, które są podzbiorem tego pierwszego. Przez ścisłe rozumiem, że powinieneś mieć dostęp do starszych wersji struktury danych bez kary, drzewo wersji może rozgałęziać się dowolnie itp.

W tym kontekście uważam, że trwałe UNION-FIND jest ważnym otwartym problemem. Istnieje artykuł Conchon-Filliâtre, o którym wspomniano w drugim wątku. Komentator już poruszył problem z tak zwaną trwałą tablicą: tak naprawdę jest tylko częściowo trwały. Załóżmy jednak, że zastąpisz go hasłem lub inną naprawdę trwałą tablicą, która zachowuje się lepiej w najgorszym (i prawdopodobnie przeciętnym) przypadku, ale gorzej w najlepszym przypadku. To wciąż pozostawia ważną kwestię otwartą:

Artykuł daje formalny dowód poprawności w Coq. Ale nie rozwiązują zamortyzowanej złożoności ani formalnie, ani nieformalnie. To bardzo dużo nie dla mnie jasne, że skomplikowana zza kulis wyniki mutacja w oczekiwany amortyzowane złożoność we wszystkich przypadkach. Kiedy po raz ostatni o tym pomyślałem, poczułem się pewnie, że mógłbym zbudować kontrprzykład, jeśli włożę w to wysiłek. Nawet jeśli się mylę co do tej ostatniej części, brak właściwej analizy stanowi poważną lukę; jasne jest, że klasyczna analiza amortyzacyjna UNION-FIND dokonana przez Trajana nie przenosi się bezpośrednio.

Jakie inne czysto funkcjonalne problemy ze strukturą danych są otwarte?

Tu jest jeden:

Jaki jest czysto funkcjonalny odpowiednik słabej tabeli skrótów?