Czysto funkcjonalna struktura danych

W informatyce czysto funkcjonalna struktura danych to taka struktura danych , którą można zaimplementować w czysto funkcjonalnym języku . Główna różnica między dowolną strukturą danych a strukturą czysto funkcjonalną polega na tym, że ta ostatnia jest (zdecydowanie) niezmienna . To ograniczenie zapewnia, że ​​struktura danych posiada zalety niezmiennych obiektów: (pełna) trwałość , szybkie kopiowanie obiektów i bezpieczeństwo wątków . Wydajne czysto funkcjonalne struktury danych mogą wymagać zastosowania leniwej oceny i zapamiętywania .

Definicja

Trwałe struktury danych mają właściwość utrzymywania swoich poprzednich wersji w niezmienionej postaci. Z drugiej strony struktury takie jak tablice dopuszczają destrukcyjną aktualizację , czyli aktualizację, której nie można cofnąć. Gdy program zapisze wartość w jakimś indeksie tablicy, nie można już odzyskać jego poprzedniej wartości. [ potrzebne źródło ]

Formalnie czysto funkcjonalna struktura danych to taka struktura danych, którą można zaimplementować w czysto funkcjonalnym języku , takim jak Haskell . W praktyce oznacza to, że struktury danych muszą być budowane wyłącznie przy użyciu trwałych struktur danych, takich jak krotki, typy sum , typy produktów oraz typy podstawowe, takie jak liczby całkowite, znaki, łańcuchy. Taka struktura danych jest z konieczności trwała. Jednak nie wszystkie trwałe struktury danych są czysto funkcjonalne. Na przykład trwała tablica to struktura danych, która jest trwała i która jest implementowana przy użyciu tablicy, a zatem nie jest czysto funkcjonalna. [ potrzebne źródło ]

W książce Czysto funkcjonalne struktury danych Okasaki porównuje destrukcyjne aktualizacje do noży mistrza kuchni. Destrukcyjnych aktualizacji nie można cofnąć, dlatego nie należy ich używać, chyba że jest pewne, że poprzednia wartość nie jest już wymagana. Jednak destrukcyjne aktualizacje mogą również pozwolić na wydajność, której nie można uzyskać za pomocą innych technik. Na przykład strukturę danych wykorzystującą tablicę i destrukcyjne aktualizacje można zastąpić podobną strukturą danych, w której tablicę zastępuje mapa , lista dostępu swobodnego lub zrównoważone drzewo , który dopuszcza czysto funkcjonalną implementację. Ale koszt dostępu może wzrosnąć od czasu stałego do czasu logarytmicznego . [ potrzebne źródło ]

Zapewnienie, że struktura danych jest czysto funkcjonalna

Struktura danych nigdy nie jest z natury funkcjonalna. Na przykład stos można zaimplementować jako listę pojedynczo połączoną . Ta implementacja jest czysto funkcjonalna, o ile jedyne operacje na stosie zwracają nowy stos bez zmiany starego stosu. Jeśli jednak język nie jest czysto funkcjonalny, system wykonawczy może nie być w stanie zagwarantować niezmienności. Ilustruje to Okasaki, gdzie pokazuje, że konkatenację dwóch pojedynczo połączonych list można nadal wykonać przy użyciu ustawienia imperatywnego. [ potrzebne źródło ]

W celu zapewnienia, że ​​struktura danych jest używana w czysto funkcjonalny sposób w nieczystym języku funkcjonalnym, moduły lub klasy mogą być używane w celu zapewnienia manipulacji wyłącznie za pośrednictwem autoryzowanych funkcji. [ potrzebne źródło ]

Używanie czysto funkcjonalnych struktur danych

Jedno z głównych wyzwań w dostosowywaniu istniejącego kodu do korzystania z czysto funkcjonalnych struktur danych polega na tym, że zmienne struktury danych zapewniają „ukryte wyjścia” dla funkcji, które ich używają. Przepisanie tych funkcji w celu korzystania z czysto funkcjonalnych struktur danych wymaga dodania tych struktur danych jako jawnych danych wyjściowych.

Rozważmy na przykład funkcję, która akceptuje zmienną listę, usuwa pierwszy element z listy i zwraca ten element. W ustawieniach czysto funkcjonalnych usunięcie elementu z listy tworzy nową i krótszą listę, ale nie aktualizuje oryginalnej. Aby więc była użyteczna, czysto funkcjonalna wersja tej funkcji prawdopodobnie będzie musiała zwrócić nową listę wraz z usuniętym elementem. W najbardziej ogólnym przypadku program przekonwertowany w ten sposób musi zwracać „stan” lub „przechowywanie” programu jako dodatkowy wynik każdego wywołania funkcji. Mówi się, że taki program jest napisany w stylu przeglądania sklepów .

Przykłady

Oto lista abstrakcyjnych struktur danych z czysto funkcjonalnymi implementacjami:

Projektowanie i wdrażanie

W swojej książce Purely Functional Data Structures informatyk Chris Okasaki opisuje techniki stosowane do projektowania i wdrażania czysto funkcjonalnych struktur danych, których niewielki podzbiór podsumowano poniżej.

Lenistwo i zapamiętywanie

Leniwa ocena jest szczególnie interesująca w czysto funkcjonalnym języku, ponieważ kolejność oceny nigdy nie zmienia wyniku funkcji. Dlatego leniwa ocena w naturalny sposób staje się ważną częścią konstrukcji czysto funkcjonalnych struktur danych. Pozwala na wykonanie obliczeń tylko wtedy, gdy ich wynik jest rzeczywiście wymagany. Dlatego kod czysto funkcjonalnej struktury danych może, bez utraty wydajności, uwzględniać w podobny sposób dane, które zostaną efektywnie wykorzystane, jak i te, które zostaną zignorowane. Jedyne wymagane obliczenia dotyczą pierwszego rodzaju danych; to właśnie zostanie wykonane. [ potrzebne źródło ]

Jednym z kluczowych narzędzi w budowaniu wydajnych, czysto funkcjonalnych struktur danych jest zapamiętywanie. Po zakończeniu obliczeń są one zapisywane i nie muszą być wykonywane po raz drugi. Jest to szczególnie ważne w leniwych implementacjach; dodatkowe oceny mogą wymagać tego samego wyniku, ale nie można wiedzieć, która ocena będzie wymagać ich w pierwszej kolejności. [ potrzebne źródło ]

Zamortyzowane analizy i harmonogramy

Niektóre struktury danych, nawet te, które nie są czysto funkcjonalne, takie jak tablice dynamiczne , dopuszczają operacje, które są wydajne przez większość czasu (np. stały czas dla tablic dynamicznych) i rzadko nieefektywne (np. czas liniowy dla tablic dynamicznych). Amortyzację można następnie wykorzystać do udowodnienia, że ​​średni czas działania operacji jest efektywny. Oznacza to, że kilka nieefektywnych operacji jest wystarczająco rzadkich i nie zmienia asymptotycznej ewolucji złożoności czasowej, gdy rozważana jest sekwencja operacji. [ potrzebne źródło ]

Ogólnie rzecz biorąc, posiadanie nieefektywnych operacji jest nie do przyjęcia dla trwałych struktur danych, ponieważ ta sama operacja może być wywoływana wiele razy. Jest to niedopuszczalne ani dla systemów czasu rzeczywistego, ani dla systemów imperatywnych, w których użytkownik może wymagać, aby czas potrzebny na wykonanie operacji był przewidywalny. Ponadto ta nieprzewidywalność komplikuje stosowanie równoległości . [ potrzebne źródło ]

Aby uniknąć tych problemów, niektóre struktury danych umożliwiają odroczenie nieefektywnej operacji — nazywa się to planowaniem . Jedynym wymaganiem jest zakończenie obliczeń nieefektywnej operacji, zanim jej wynik będzie faktycznie potrzebny. Stała część nieefektywnej operacji jest wykonywana jednocześnie z następującym po niej wezwaniem do efektywnej operacji, tak że nieefektywna operacja jest już całkowicie wykonana, kiedy jest potrzebna, a każda pojedyncza operacja pozostaje wydajna. [ wymagane wyjaśnienie ]

Przykład: kolejka

Kolejki amortyzowane składają się z dwóch pojedynczo połączonych list: przedniej i odwróconej tylnej. Elementy są dodawane do tylnej listy i usuwane z przedniej listy. Ponadto, gdy przednia kolejka jest pusta, tylna kolejka jest odwracana i staje się przednią, podczas gdy tylna kolejka staje się pusta. Zamortyzowana złożoność czasowa każdej operacji jest stała. Każda komórka listy jest dodawana, odwracana i usuwana maksymalnie raz. Aby uniknąć nieefektywnej operacji, w której tylna lista jest odwrócona, kolejki w czasie rzeczywistym dodaj ograniczenie, że lista tylna jest tak długa, jak lista przednia. Aby lista tylna była dłuższa niż lista przednia, lista przednia jest dołączana do listy tylnej i odwracana. Ponieważ ta operacja jest nieefektywna, nie jest wykonywana natychmiast. Zamiast tego jest rozłożony na kolejne operacje. W ten sposób każda komórka jest obliczana, zanim będzie potrzebna, a nowa pierwsza lista jest całkowicie obliczana, zanim trzeba będzie wywołać nową nieefektywną operację. [ potrzebne źródło ]

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Purely_functional_data_structure&oldid=1090910023 ”