Jak czysto funkcjonalne języki programowania radzą sobie z szybko zmieniającymi się danymi?

Jakich struktur danych można użyć, aby uzyskać usunięcie i zastąpienie O (1)? Lub jak uniknąć sytuacji, w których potrzebujesz wspomnianych struktur?

Istnieje szeroki wachlarz struktur danych wykorzystujących lenistwo i inne sztuczki w celu osiągnięcia zamortyzowanego stałego czasu lub nawet (w niektórych ograniczonych przypadkach, takich jak kolejki ) stałych aktualizacji czasu dla wielu rodzajów problemów. Rozprawa doktorska Chrisa Okasakiego „Czysto funkcjonalne struktury danych” i książka o tym samym tytule są najlepszym przykładem (być może pierwszym znaczącym), ale od tego czasu dziedzina się rozwinęła . Te struktury danych są zazwyczaj nie tylko funkcjonalne w interfejsie, ale mogą być również implementowane w czystym języku Haskell i podobnych językach i są w pełni trwałe.

Nawet bez tych zaawansowanych narzędzi proste zrównoważone drzewa wyszukiwania binarnego zapewniają aktualizacje w czasie logarytmicznym, więc pamięć zmienna może być symulowana przy najgorszym spowolnieniu logarytmicznym.

Istnieją inne opcje, które można uznać za oszustwo, ale są bardzo skuteczne w odniesieniu do wysiłków wdrożeniowych i wydajności w świecie rzeczywistym. Na przykład typy liniowe lub typy unikatowości umożliwiają aktualizację w miejscu jako strategię implementacji dla koncepcyjnie czystego języka, uniemożliwiając programowi zachowanie poprzedniej wartości (pamięci, która zostałaby zmutowana). Jest to mniej ogólne niż trwałe struktury danych: na przykład nie można łatwo zbudować dziennika cofania, przechowując wszystkie poprzednie wersje stanu. To wciąż potężne narzędzie, chociaż AFAIK nie jest jeszcze dostępny w głównych językach funkcjonalnych.

Inną opcją bezpiecznego wprowadzenia stanu zmiennego do ustawienia funkcjonalnego jest STmonada w Haskell. Może być zaimplementowany bez mutacji i blokowania unsafe*funkcji, zachowuje się tak, jakby był tylko fantazyjnym opakowaniem dookoła, przekazując niejawnie trwałą strukturę danych (por State.). Ale ze względu na pewien rodzaj oszustwa systemowego, który wymusza porządek oceny i zapobiega ucieczce, można go bezpiecznie wdrożyć za pomocą mutacji w miejscu, ze wszystkimi korzyściami w zakresie wydajności.

Jedną tanią zmienną strukturą jest stos argumentów.

Spójrz na typowe obliczenia czynnikowe w stylu SICP:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

Jak widać, drugi argument facsłuży jako zmienny akumulator zawierający szybko zmieniający się produkt n * (n-1) * (n-2) * .... Nie widać jednak żadnej zmiennej zmiennej i nie ma sposobu, aby przypadkowo zmienić akumulator np. Z innego gwintu.

Jest to oczywiście ograniczony przykład.

Możesz uzyskać niezmienne połączone listy z tanią wymianą węzła głównego (a przez to dowolną część zaczynającą się od głowy): po prostu ustaw nowy punkt główny na ten sam następny węzeł, co poprzedni. Działa to dobrze z wieloma algorytmami przetwarzania list (w foldoparciu o cokolwiek ).

Możesz uzyskać całkiem dobrą wydajność z tablic asocjacyjnych opartych np. Na HAMT . Logicznie otrzymujesz nową tablicę asocjacyjną ze zmienionymi niektórymi parami klucz-wartość. Implementacja może współdzielić większość wspólnych danych między starymi i nowo utworzonymi obiektami. Nie jest to jednak O (1); zwykle dostajesz coś logarytmicznego, przynajmniej w najgorszym przypadku. Z kolei niezmienne drzewa zwykle nie ponoszą żadnych strat wydajnościowych w porównaniu z drzewami zmiennymi. Oczywiście wymaga to trochę narzutu pamięci, zwykle dalekiego od wygórowanego.

Inne podejście opiera się na założeniu, że jeśli drzewo spada w lesie i nikt go nie słyszy, nie musi wytwarzać dźwięku. Oznacza to, że jeśli możesz udowodnić, że trochę zmutowanego stanu nigdy nie opuszcza jakiegoś lokalnego zasięgu, możesz bezpiecznie zmutować dane w nim zawarte.

Clojure ma stany przejściowe, które są zmiennymi „cieniami” niezmiennych struktur danych, które nie przeciekają poza zasięg lokalny. Clean używa Unikatów, aby osiągnąć coś podobnego (jeśli dobrze pamiętam). Rdza pomaga robić podobne rzeczy za pomocą statycznie sprawdzanych unikalnych wskaźników.

To, o co pytasz, jest trochę za szerokie. O (1) usunięcie i wymiana z jakiej pozycji? Szef sekwencji? Ogon? Dowolne stanowisko? Wykorzystywana struktura danych zależy od tych szczegółów. To powiedziawszy, 2-3 drzewa palcowe wydają się jedną z najbardziej wszechstronnych trwałych struktur danych:

Prezentujemy 2-3 drzewa palców, funkcjonalną reprezentację trwałych sekwencji wspierających dostęp do końców w zamortyzowanym stałym czasie, oraz konkatenację i podział logarytmiczny czasowy wielkości mniejszego kawałka.

(...)

Ponadto, definiując operację podziału w formie ogólnej, uzyskujemy strukturę danych ogólnego przeznaczenia, która może służyć jako sekwencja, kolejka priorytetów, drzewo wyszukiwania, kolejka wyszukiwania priorytetów i więcej.

Generalnie trwałe struktury danych mają wydajność logarytmiczną przy zmianie dowolnych pozycji. Może to stanowić problem, ale może nie być problemem, ponieważ stała w algorytmie O (1) może być wysoka, a spowolnienie logarytmiczne może zostać „wchłonięte” w wolniejszy algorytm.

Co ważniejsze, trwałe struktury danych ułatwiają rozumowanie na temat programu i zawsze powinien to być domyślny tryb działania. Powinieneś faworyzować trwałe struktury danych, gdy tylko jest to możliwe, i używaj modyfikowalnej struktury danych tylko wtedy, gdy profilujesz i ustalisz, że trwała struktura danych stanowi wąskie gardło wydajności. Wszystko inne to przedwczesna optymalizacja.