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

51

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?

jbapple
źródło
Rozumiem, że masz na myśli próby jak w drzewach skrótów zamiast bardziej ogólnych słowników z kluczami, które są sekwencjami? FWIW, myślę, że nie można tutaj podejść do starej dobrej tabeli skrótów.
Jon Harrop

Odpowiedzi:

19

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.

na Vognsen
źródło
5
Jeden kandydat na w pełni trwałe (ale nie konfluentnie trwałe) tablice jest przedstawiony w Confluently Persistent Tries for Efficient Version Control . Autorzy twierdzą, że spowolnienie O (lg lg n), pokonując spowolnienie O (lg mg) Dietza i innych, gdzie m jest liczbą operacji wykonanych na macierzy.
jbapple
1
Dodam również, że chociaż leniwe, zamortyzowane struktury Okasaki są często znacznie prostsze niż alternatywy, nie znam żadnej struktury danych, która mogłaby zostać zaimplementowana w ten sposób, która również nie mogłaby zostać zaimplementowana (z tymi samymi granicami czasowymi, ale najgorszy przypadek) w naprawdę czysto funkcjonalny sposób.
jbapple
12

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

Tu jest jeden:

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

Jon Harrop
źródło
15
um ... PO poprosił o pytania bez odpowiedzi, więc kwalifikowałoby się to jako potencjalna odpowiedź na pytanie PO.
Jason S
6
Dobra, ugryzę. Co to jest słaby stół mieszający?
Jeffε
4
Jest to tablica skrótów, która pozwala na zbieranie śmieci, jeśli tylko ona (i inne słabe mapy) zawierają odniesienia do niej.
Havvy,
3
@JonHarrop: łatwo jest udowodnić, że czysta wersja słabego odwołania jest niemożliwa, ponieważ słabe odniesienia sprawiają, że semantyka języka jest niedeterministyczna, a czysto funkcjonalne języki są deterministyczne. Jeśli dodatkowo zaznaczysz niedeterminizm w typie, wówczas działa normalna implementacja. Potrzebujesz typów zależnych (aby udowodnić, że implementacja daje te same odpowiedzi niezależnie od treści odwołania), jeśli chcesz bezpiecznie maskować efekt.
Neel Krishnaswami,
5
@NeelKrishnaswami, nie sądzę, że tak jest. Możesz tworzyć słabe struktury danych, które nie powodują niedeterminizmu, takie jak słaba tabela, która nie obsługuje wyliczania (ani zliczania). Zobacz wiki.ecmascript.org/doku.php?id=harmony:weak_maps dla przykładu.
Sam Tobin-Hochstadt