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

22

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?

mrpyo
źródło
2
Czy dla tych z nas, którzy są mniej zaznajomieni z czysto funkcjonalnymi językami programowania, możesz podać nieco więcej informacji, abyśmy mogli zrozumieć, na czym polega Twój problem?
FrustratedWithFormsDesigner
4
@FrustratedWithFormsDesigner Czysto funkcjonalne języki programowania wymagają, aby wszystkie zmienne były niezmienne, co z kolei wymaga struktur danych, które po zmodyfikowaniu tworzą nowe wersje samych siebie.
Doval
5
Czy zdajesz sobie sprawę z pracy Okasaki nad czysto funkcjonalnymi strukturami danych?
2
Jedną z możliwości jest zdefiniowanie monady dla zmiennych danych (patrz np. Haskell.org/ghc/docs/4.08/set/sec-marray.html ). W ten sposób zmienne dane są traktowane podobnie jak IO.
Giorgio
1
@CodesInChaos: jednak takie niezmienne struktury zwykle mają również znacznie większy narzut niż proste tablice. W rezultacie, nie jest bardzo praktyczna różnica. Dlatego każdy język o czysto funkcjonalnym charakterze, który ma na celu programowanie ogólnego przeznaczenia, powinien mieć możliwość korzystania ze struktur zmiennych, w bezpieczny sposób zgodny z czystą semantyką. STMonada w Haskell robi to doskonale.
leftaroundabout

Odpowiedzi:

32

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.

Społeczność
źródło
Warto również wspomnieć o Zamkach błyskawicznych, które umożliwiają szybkie wprowadzanie zmian w centrum uwagi na liście lub drzewie
jk.
1
@jk. Są one wspomniane w poście z teoretycznej informatyki, do którego linkowałem. Co więcej, są tylko jedną (no cóż, klasą) wieloma odpowiednimi strukturami danych i omawianie ich wszystkich jest poza zakresem i mało przydatne.
uczciwie, nie podążałem za linkami
jk.
9

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.

9000
źródło
1
+1, również za wymienienie unikalnych typów w Czystości.
Giorgio
@ 9000 Wydaje mi się, że słyszałem, że Haskell ma coś podobnego do stanów przejściowych Clojure - ktoś mnie poprawia, jeśli się mylę.
Paul
@paul: Mam bardzo pobieżną wiedzę na temat Haskell, więc jeśli możesz podać moje informacje (przynajmniej słowo kluczowe w Google), chętnie dołączę odniesienie do odpowiedzi.
9000
1
@paul Nie jestem tego taki pewien. Ale Haskell ma metodę tworzenia czegoś podobnego do ML refi ograniczania ich w pewnym zakresie. Zobacz IOReflub STRef. A potem oczywiście są TVarsi i MVarpodobne, ale z rozsądną równoczesną semantyką (stm dla TVarsi i muteks oparty na MVars)
Daniel Gratzer
2

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.

Doval
źródło