Dlaczego programowanie funkcjonalne nie badało dynamicznych drzew?

19

Drzewa dynamiczne odgrywają ważną rolę w rozwiązywaniu problemów, takich jak przepływy sieciowe, wykresy dynamiczne, problemy kombinatoryczne („Drzewa dynamiczne w praktyce” Tarjana i Wernecka) oraz ostatnio łączone słowniki („Prosty słownik łączący” Adama Karczmarza),

Przez drzewa dynamiczne odwołuję się do definicji podanej w dokumencie Sleator & Tarjan zatytułowanym „Struktura danych dla drzew dynamicznych” z 1983 r. Od tego czasu opublikowano niewiele wysiłków w dziedzinie badań nad programowaniem funkcjonalnym.

  1. Edward Kmett zaimplementował wersję drzewek ST głównie jako tłumaczenie odpowiednika C ++, patrz Drzewa cięte linkami .
  2. Chris Okasaki napisał ograniczoną implementację drzew Splay w swojej znanej książce „Czysto funkcjonalne struktury danych”.
  3. Ralf Hinze i Ross Paterson wprowadzili funkcjonalną strukturę danych zwaną 2-3 palcami, ale z nieco innym celem niż pierwotna definicja dynamicznych drzew.

Implementacja (i być może wydajność) dynamicznych drzew jest podzielona według trzech podejść:

  1. Linearyzacja, w której drzewa ET (Euler tour) odgrywają wielką rolę. Nie znaleziono czysto funkcjonalnego badania.
  2. Rozkład ścieżek, w którym drzewa ST są flagowym produktem, właśnie znalazł wersję Kmetta.
  3. Skurcz drzewa, w którym gracze zajmują drzewa najlepsze, drzewa topologiczne i drzewa RC. Nie znaleziono czysto funkcjonalnego badania.

Czysto funkcjonalną analizę i implementację można znaleźć na Splay, AVL, czerwono-czarnym drzewie, ale NIE są to drzewa dynamiczne. Te pierwsze są uważane za cień (zwaną także wirtualną lub pomocniczą) strukturą danych tego drugiego.

Moje pytanie brzmi:

Jakie są przyczyny (wady, wady) społeczności badawczej ds. Programowania funkcjonalnego, która nie bierze udziału w strukturze danych dynamicznych drzew?

data-structures trees functional-programming Richard Chambers
źródło
14
Nie rozumiem, jak można na to odpowiedzieć bez utworzenia Autorytatywnego Komitetu Społecznego Programowania Funkcjonalnego w celu formułowania oficjalnych opinii. Czy nie możemy przeformułować pytania, aby znaleźć odpowiedź na pytanie? O ile mi wiadomo, PO powinien po prostu wdrożyć swoje dynamiczne drzewa w Haskell lub czymkolwiek, a następnie wrócić tutaj, aby zgłosić, że zostało to zrobione.
Andrej Bauer,
Aktualizacja @AndrejBauer: PO upadł i realizowane w jego drzew dynamicznych Haskell: arxiv.org/abs/1908.11105
jbapple

Odpowiedzi:

-1

„W informatyce programowanie funkcjonalne jest paradygmatem programowania. Styl budowania struktury i elementów programów komputerowych, który traktuje obliczenia jako ocenę funkcji matematycznych i unika zmieniania stanu i zmiennych danych”. - Wikipedia

„zmiana stanu i danych zmiennych”, innymi słowy „dynamiczny”.

Więc twoje pytanie jest trochę jak pytanie, dlaczego lewica jest niewłaściwa.

Anthony Bachler
źródło
1
Programy funkcjonalne mogą reprezentować dane dynamiczne z trwałymi strukturami danych. To pytanie nasuwa pytanie, dlaczego nie opracowano rozwoju trwałych struktur danych dla określonego problemu. Pytanie ma sens.
Przywróć Monikę