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,IntMaplubHashMap) 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”.Odpowiedzi:
Mogą istnieć inne wydajne niezmienne struktury danych, które pasują do konkretnego zadania, ale nie są tak ogólne jak podwójnie połączona lista (która niestety jest podatna na błędy w modyfikacji modyfikacji ze względu na jej zmienność). Jeśli zawęzisz swój problem, prawdopodobnie znajdziesz taką strukturę.
Ogólną odpowiedzią na (względnie) ekonomiczne przechodzenie niezmiennych struktur są soczewki. Chodzi o to, że możesz zachować wystarczającą ilość informacji, aby zrekonstruować zmodyfikowaną niezmienną strukturę z jej niezmodyfikowanych części i aktualnie zmodyfikowanego elementu, i nawigować nad nią do sąsiedniego węzła.
Kolejną przydatną strukturą jest zamek błyskawiczny . (Zabawne jest to, że podpis typu dla zamka błyskawicznego do
obiektywujest pochodną matematyki szkoły od podpisu typu struktury).Oto kilka linków.
Rozdział dotyczący zamków błyskawicznych z „Learn you a Haskell”
Wprowadzenie do soczewek w Scali (slajdy)
źródło
Haskell nie zabrania używania zmiennych struktur danych. Są one mocno zniechęcone i trudniejsze w użyciu, ponieważ części kodu, które ich używają, muszą ostatecznie zwrócić akcję IO (która ostatecznie musi być powiązana z akcją IO zwracaną przez funkcję główną), ale to nie oznacza uniemożliwić korzystanie z takich struktur, jeśli naprawdę ich potrzebujesz.
Sugerowałbym zbadanie wykorzystania programowej pamięci transakcyjnej jako drogi naprzód. Zapewnia nie tylko skuteczny sposób implementacji struktur zmiennych, ale także zapewnia bardzo przydatne gwarancje bezpieczeństwa wątków. Zobacz opis modułu na https://hackage.haskell.org/package/stm i przegląd wiki na https://wiki.haskell.org/Software_transactional_memory .
źródło
MVar,State,ST), więc będę musiał zorientować się ich różnic i planowanych zastosowań.STIMO, należy o tym wspomnieć w odpowiedzi, ponieważ pozwala ona uruchomić obliczenia stanowe, a następnie wyrzucić stan i wyodrębnić wynik jako czystą wartość.STz STM, aby mieć zarówno współbieżność, jak i stan jednorazowy?mainzmiennej. :) (mainnawet nie pełni żadnej funkcji)