Jakie są korzyści z czysto funkcjonalnej struktury danych?

Oprócz bezpieczeństwa pamięci współdzielonej większość czysto funkcyjnych struktur danych daje również trwałość i praktycznie za darmo. Na przykład, powiedzmy, że mam set w OCaml, i chcę dodać do niego kilka nowych wartości, mogę to zrobić:

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

a pozostaje niezmodyfikowane po dodaniu nowych znaków (zawiera tylko A-d), podczas gdy b zawiera a-h i dzielą część tej samej pamięci (z set jest trochę trudno powiedzieć, ile pamięci jest współdzielone od jest to drzewo AVL i kształt drzewa się zmienia). Mogę nadal to robić, śledząc wszystkie zmiany, które wprowadziłem w drzewie, pozwalając mi wrócić do poprzedniego stanu.

Oto wielki diagram z artykułu Wikipedii na temat czysto funkcjonalnych, który pokazuje wyniki wstawiania znaku " e " do drzewa binarnego xs:

Programy Erlang używają czysto funkcjonalnych struktur danych niemal wyłącznie i czerpią znaczne korzyści, skalując je niemal płynnie do wielu rdzeni. Ponieważ współdzielone dane (głównie binaria i ciągi bitowe) nigdy nie są modyfikowane, nigdy nie ma potrzeby blokowania takich danych.

Weź ten mały fragment F#:

let numbers = [1; 2; 3; 4; 5]

Można powiedzieć ze 100% pewnością, że jest to niezmienna lista liczb całkowitych od 1 do 5. Możesz przekazać odniesienie do tej listy i nigdy nie musisz się martwić, że lista mogła zostać zmodyfikowana. To wystarczający powód, by go użyć.

Czysto funkcjonalne struktury danych mają następujące zalety:

• Trwałość: stare wersje mogą być bezpiecznie używane ze świadomością, że nie mogły zostać zmienione.

• Udostępnianie: wiele wersji struktury danych może być przechowywanych jednocześnie przy niewielkich wymaganiach dotyczących pamięci.

• Bezpieczeństwo wątku: każda mutacja jest ukryta wewnątrz lazy thunks (jeśli istnieje) i dlatego jest obsługiwana przez implementację języka.

• Prostota: brak konieczności śledzenia zmian stanu sprawia, że czysto funkcjonalne struktury danych są prostsze w użyciu, szczególnie w kontekście współbieżności.

• Inkrementalność: czysto funkcjonalne struktury danych składają się z wielu drobnych części, co czyni je idealnymi do przyrostowego zbierania śmieci, co prowadzi do mniejszych opóźnień.

Zauważ, że nie wymieniłem paralelizmu jako przewagi czysto funkcjonalnych struktur danych, ponieważ nie sądzę, aby tak było. Wydajny równoległość wielordzeniowa wymaga przewidywalnej lokalizacji w celu wykorzystania pamięci podręcznej i uniknięcia wąskiego gardła w dostępie do pamięci głównej, a czysto funkcjonalne struktury danych mają w najlepszym razie nieznane Cechy pod tym względem. W związku z tym wiele programów, które używają czysto funkcjonalnych struktur danych, nie skaluje się dobrze, gdy są równoległe do wielordzeniowego, ponieważ cały swój czas spędzają w pamięci podręcznej, walcząc o wspólne ścieżki pamięci.

Co mam na myśli mówiąc czysto funkcjonalna struktura danych nie jest taka sama jak struktura danych trwałych.

Jest tu trochę zamieszania. W kontekście czysto funkcjonalnych struktur danych, trwałość jest terminem używanym w odniesieniu do możliwości odwoływania się do poprzednich wersji struktury danych bezpiecznych ze świadomością, że są one nadal ważne. Jest to naturalny wynik bycia czysto funkcjonalnym, a zatem trwałość jest nieodłączną cechą wszystkich czysto funkcjonalnych struktur danych.