Mutowalność w programowaniu funkcjonalnym

Question

Najpierw jestem nowicjuszem Haskell. Przeczytałem to: Immutable functional objects in highly mutable domain Moje pytanie jest prawie takie samo - jak wydajnie pisać algorytmy, w których stan ma się zmienić. Weźmy na przykład algorytm Dijkstry. Zostaną znalezione nowe ścieżki, a odległości powinny zostać zaktualizowane. W tradycyjnych językach jest to proste, podczas gdy w Haskell na przykład mogę myśleć tylko o stworzeniu zupełnie nowych odległości, które będą zbyt wolne i będą pochłaniały pamięć. Czy są takie wzorce projektowe dla takich przypadków, w których należy wdrożyć algorytm z zmienną strukturą danych, a szybkość i wykorzystanie pamięci są głównymi problemami?

Answer 1

Istnieje oczywiście wiele sposobów na rozwiązywanie tego problemu przez języki funkcjonalne.

1. Różne struktury danych - struktury wiele danych mogą być realizowane w czysto funkcjonalnego sposób, z tym samym algorytmicznej złożoności jako wersje nadrzędnymi. Prawdopodobnie najbardziej znanym dziełem w tym obszarze jest Chris Okasaki Purely Functional Data Structures, ale jest też wiele innych zasobów. Dla algorytmu Dijkstry odpowiednia jest praca Martin Erwig pod numerem functional graphs. Zobacz także this question.

2. Różne algorytmy - niektóre algorytmy mają założenia wbudowanej zmienności, Quicksort jest tego przykładem. W takim przypadku można zastosować alternatywny algorytm, który jest bardziej podatny na niezmienność.

3. Stan zmutowalny - każdy język funkcyjny może modelować stan funkcjonalny z monadą państwową. Większość dostarcza także innych form zmienności, takich jak moneta Haskella i IORef.

Answer 2

Urządzenie ST Monad umożliwia wewnętrznie używanie stanu zmiennego, ale przedstawia wyłącznie interfejs zewnętrzny.

Answer 3

Tworzenie nowych niezmiennych obiektów nie jest prawie takim samym kosztem, jak mogłoby się wydawać, ponieważ duże ilości współdzielenia strukturalnego mogą wystąpić, ponieważ kompilator wie, że nie może się zmienić, a zatem może być bezpiecznie udostępniony. To powiedziawszy, użycie wysoce imperatywnych algorytmów z dużą ilością zmiennego stanu w Haskell to trochę zakodowany kod.

Answer 4

W pochodnych ML (takich jak OCaml, SML, F #) istnieją "referencje", które można wykorzystać jako zmienne zmienne.

W Haskell nie jest to obsługiwane w czysty sposób. Państwo po prostu nie jest objęte zwykłym stylem "czysto funkcjonalnym". Czyste języki FP radzą sobie z "odwiecznymi prawdami" i dlatego nie nadają się do pracy z "efemerycznymi prawdami" (choć można to z całą pewnością zrobić).

Jednak tak, czasami potrzebujemy zmiennego stanu. Język taki jak ATS zawiera typy liniowe do obsługi destrukcyjnych aktualizacji i bezpiecznej manipulacji zasobami.