Czy jest możliwe posiadanie listy podwójnie powiązanych w Haskell i jakie jest idealne rozwiązanie do ich realizacji? Wdrażam wykres sceny, w którym każdy widget ma zarówno rodzica, jak i dziecko, i dobrze jest patrzeć w górę i w dół wykresu.jak zaimplementować podwójnie powiązane listy
Nie jest praktycznie praktycznym posiadanie podwójnie połączonej listy w Haskell, ponieważ musisz ją zbudować naraz.
Na przykład wyobraź sobie, że masz listę [1, 2, 3, 4, 5], którą chcesz podwójnie połączyć. Teraz wyobraźmy sobie, jak lista jest reprezentowana:
data DoubleList a
= LeftEnd a (DoubleList a)
| Middle a (DoubleList a) (DoubleList a)
| RightEnd a (DoubleList a)
(używam dwóch różnych konstruktorów dla dwóch końcach dla uproszczenia)
Aby zbudować listę powyżej, trzeba najpierw zbudować pierwszy element:
let e1 = LeftEnd 1 ...
Ale do skonstruowania pierwszego elementu, to już trzeba mieć drugi element:
let e1 = LeftEnd 1 e2
e2 = Middle 2 e1 ...
A dla drugiego elementu, trzeba trzeci itd:
let e1 = LeftEnd 1 e2
e2 = Middle 2 e1 e3
e3 = Middle 3 e2 e4
e4 = Middle 4 e3 e5
e5 = RightEnd 5 e4
Jest to możliwe do zrobienia w Haskell spowodowane oceny leniwy; ta strategia nazywa się "wiązaniem węzła" (i nie musisz dosłownie umieszczać wszystkiego w jednym bloku let, możesz podzielić konstrukcję na funkcje)
Ale, innymi słowy, zrobić podwójnie Jeśli chcesz zmienić dowolną jego część, musisz albo użyć jej Zipper, albo po prostu wykonać pełną kopię za każdym razem.
Polecam zamiast tego użyć Data.Sequence, która jest zoptymalizowaną implementacją sekwencyjnego przechowywania w oparciu o drzewo palców. Obsługuje bardzo szybkie wstawianie, usuwanie i iterację, przy czym wciąż jest czysto funkcjonalną strukturą danych.
W przeciwnym razie możesz po prostu użyć suwaków, ale użyj ich zamiast drzewa dla list. Więcej informacji o Zippers można znaleźć na Haskell Wiki. Zamki doskonale pasują do tej sytuacji, ponieważ oferują dokładnie taką funkcjonalność, jakiej potrzebujesz: jeśli odwiedzasz drzewo z zamkiem błyskawicznym, zyskujesz dostęp do "rodziców" części drzewa, które odwiedzasz, ale samo drzewo nie musi zawierać odniesień nadrzędnych.
Jeśli chodzi o budowanie podwójnie powiązane lista z listy ('[a]'), [tutaj] (http://rosettacode.org/wiki/Doubly-Linked_List_%28traversal%29#Haskell) jeden fragment kodu; jest to funkcja "create". – Vitus
fajny dla Data.Sequence! Teraz jest ciekawy typ! Również Szybki dostęp do obu końców listy, który był dokładnie tym, po czym byłem –
Ponieważ w Haskell nie ma (zwykle) obiektów w stylu OO, dziwne jest myślenie, że dane są samoświadome. Należy pamiętać, że zazwyczaj nie używa się agregacji w typach danych Haskell, zamiast tego faworyzuje kompozycję.
Możesz zajrzeć do XMonad, aby sprawdzić, czy ich projekt pasuje do twoich potrzeb (kod jest zaskakująco czytelny).
Możesz także zrestrukturyzować swój projekt, aby nigdy nie trzeba było patrzeć ponad tobą (na przykład przekazując dzieciom "oddzwonienia").
Możesz również sprawdzić, czy możesz napisać suwak dla całego wykresu.
Przykro mi być pedantycznym, ale IMHO nazywa listy "powiązanych list" lub mówi o "podwójnie powiązanych listach" w kontekście czystego FP, przeciąga wiele imperatywnego bagażu (wskaźników, destrukcyjnych aktualizacji) do dyskusji i dezorientuje rzeczy. – jberryman
Cel dla ciebie, jeśli nie bezpośrednio na twoje pytanie ... W dokumencie "Ogromne dane, ale małe programy" zamieszczono wykres sceny http://eprints.whiterose.ac.uk/5000/ - kod powinien, miejmy nadzieję, nadal być publicznie dostępne, ale nigdy nie zostały wprowadzone w Hackage. Niestety, wydaje się, że nie ma zbyt wielu opublikowanych prac dotyczących tej dziedziny z funkcjonalnym programowaniem, szkoda, bo to świetny temat. –
Zamiast używania listy podwójnie połączonej, w haskell jest znacznie łatwiej przechowywać dane w postaci pojedynczo połączonego drzewa, a następnie przechodzić przez nie [zipper] (http://learnyouahaskell.com/zippers) – rampion