Chciałbym dowiedzieć się, jak tworzyć wykresy i wykonywać na nich pewne lokalne operacje w Haskell, ale pytanie nie jest specyficzne dla Haskell i zamiast wykresów możemy rozważyć podwójnie połączone listy.
Pytanie: Jaki byłby idiomatyczny lub zalecany sposób wdrożenia podwójnie powiązanej listy (lub innej podwójnie powiązanej lub okrągłej struktury danych) i operacji na niej w języku, który głównie obsługuje i zaleca niezmienne struktury danych (Haskell, Clojure itp.) ? W szczególności, jak korzystać z aktualizacji lokalnych, które są formalnie zabronione przez język?
Mogę łatwo wyobrazić sobie, że jeśli jakieś operacje lokalne są wykonywane na podwójnie połączonej liście (na przykład, jeśli wstawiony jest element), może nie być konieczne kopiowanie całej listy natychmiast z powodu lenistwa języka. Ponieważ jednak lista jest podwójnie połączona, jeśli zostanie zmodyfikowana w jednym miejscu, żaden ze starych węzłów nie będzie mógł zostać użyty w nowej wersji listy, a prędzej czy później trzeba by je jakoś oznaczyć, skopiować, wyrzucić śmieci. . Oczywiście są to operacje zbędne, jeśli zostanie użyta tylko zaktualizowana kopia listy, ale dodają „koszty ogólne” proporcjonalne do wielkości listy.
Czy to oznacza, że do takich zadań niezmienne dane są po prostu nieodpowiednie, a funkcjonalne języki deklaratywne bez „natywnej” obsługi danych zmiennych nie są tak dobre, jak te niezbędne? Czy jest jakieś trudne obejście?
PS Znalazłem kilka artykułów i prezentacji na ten temat w Internecie, ale miałem trudności z ich śledzeniem, podczas gdy myślę, że odpowiedź na to pytanie nie powinna zająć więcej niż jednego akapitu i może diagramu ... to znaczy, jeśli jest nie ma „funkcjonalnego” rozwiązania tego problemu, odpowiedź prawdopodobnie brzmi „użyj C”. Jeśli istnieje, to jak skomplikowane może być?
Powiązane pytania
„Struktury danych w programowaniu funkcjonalnym” . Moje szczegółowe pytanie dotyczące używania aktualizacji w miejscu zamiast nieefektywnych alternatyw nie jest tutaj omawiane.
„Wewnętrzna mutacja trwałych struktur danych” . Tam wydaje się, że nacisk kładziony jest na implementację niskiego poziomu w nieokreślonym języku, podczas gdy moje pytanie dotyczy właściwego wyboru języka (funkcjonalnego lub innego) i możliwych rozwiązań idiomatycznych w językach funkcjonalnych.
Odpowiednie cytaty
Czysto funkcjonalne języki programowania umożliwiają bardzo zwięzłe wyrażanie wielu algorytmów, ale istnieje kilka algorytmów, w których zdatny do aktualizacji stan wydaje się odgrywać kluczową rolę. W przypadku tych algorytmów języki czysto funkcjonalne, które nie mają stanu umożliwiającego aktualizację, wydają się z natury nieefektywne ( [Ponder, McGeer i Ng, 1988] ).
- John Launchbury i Simon Peyton Jones, Lazy wątki stanu funkcjonalnego (1994), a także John Launchbury i Simon Peyton Jones, stan w Haskell (1995). Te prace przedstawiają STkonstruktor typu monadycznego w Haskell.
DiffArraytyp. Patrząc na źródło z diffarray pakietu, widzę 91 wystąpień unsafePerformIO. Wygląda na to, że odpowiedź na moje pytanie brzmi „tak, nie, czysto funkcjonalne języki z niezmiennymi danymi nie są odpowiednie do implementacji algorytmów, które zwykle polegają na aktualizacjach w miejscu”.
Map, IntMaplub HashMap) jako pamięci i tworzeniu węzłów zawierających identyfikatory połączonych węzłów. „Wszystkie problemy w informatyce można rozwiązać przez inny poziom pośredni”.