Lista podwójnie powiązana w czysto funkcjonalnym języku programowania
Jak zrobić podwójnie połączone listy w czystym funkcjonalnym języku? To znaczy, coś jak Haskell, gdzie nie jesteś w Monadzie, więc nie masz mutacji. Czy to możliwe? (Pojedynczo powiązana lista jest oczywiście dość łatwa).
4 answers
W czystym języku funkcjonalnym, podwójnie powiązana lista nie jest aż tak interesująca. Idea podwójnie połączonej listy polega na tym, aby móc złapać węzeł i iść w dowolnym kierunku, lub aby móc połączyć się na środku listy. W czystym języku funkcyjnym prawdopodobnie lepiej jest mieć jedną z tych dwóch struktur danych:
Pojedynczo powiązana lista ze wskaźnikiem w środku, z którego można przejść w lewo lub w prawo (wariant "Zipper " Hueta")
A finger tree, która jest oszałamiającą strukturą danych wymyśloną przez Ralfa Hinze i Rossa Patersona.
Jestem wielkim fanem zamka błyskawicznego; przydaje się w wielu sytuacjach.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-12-04 03:15:48
Istnieje wiele podejść.
Jeśli nie chcesz zmutować podwójnie połączonej listy po jej zbudowaniu, możesz po prostu "zawiązać węzeł", polegając na lenistwie.
Http://www.haskell.org/haskellwiki/Tying_the_Knot
Jeśli chcesz mieć zmienną listę podwójnie połączoną, musisz jakoś sfałszować referencje -- lub użyć prawdziwych -- a la sztuczka zaproponowana przez Olega Kisejłowa i zaimplementowana tutaj:
Http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html
Co ciekawe, zauważ, że pierwsze opiera się zasadniczo na lenistwie, aby odnieść sukces. Ostatecznie potrzeba mutacji lub lenistwa, aby zawiązać węzeł.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-03-17 16:07:49
[1]}powtórzę pytanie musicfana: "po co ci to dokładnie?"Jak zauważa Norman Ramsey: jeśli potrzebujesz wielokierunkowego przesuwu, zamki błyskawiczne są łatwiejsze; jeśli potrzebujesz szybkiego łączenia, drzewa palcowe działają dobrze.
Ale żeby zobaczyć jak to wygląda...import Control.Arrow
import Data.List
data LNode a = LNode { here :: a, prev :: LList a, next :: LList a }
type LList a = Maybe (LNode a)
toList :: LList a -> [a]
toList = unfoldr $ fmap $ here &&& next
fromList :: [a] -> LList a
fromList l = head nodes where
nodes = scanr ((.) Just . uncurry LNode) Nothing $ zip l $ Nothing : nodes
append :: LList a -> LList a -> LList a
append = join Nothing where
join k (Just a) b = a' where
a' = Just $ a { prev = k, next = join a' (next a) b }
join k _ (Just b) = b' where
b' = Just $ b { prev = k, next = join b' Nothing (next b) }
join _ _ _ = Nothing
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-12-04 17:13:56
W OCaml, dla circular simply linked list zawsze możesz zrobić coś takiego:
type t = { a : t Lazy.t }
let cycle n =
let rec start = {a = lazy (aux n) }
and aux = function
| 0 -> start
| n -> { a = lazy (aux (n-1))}
in start
Dla podwójnie połączonych list, wyobrażam sobie, że można zrobić coś podobnego. Ale musisz polegać na lenistwie i na tym, że zapisy są przyjaznymi strukturami, jeśli chodzi o pisanie. Szybka i brudna lista cyklicznie linkowana:
type 'a t = { data : 'a; before : 'a t Lazy.t; after : 'a t Lazy.t }
let of_list l =
match l with [] -> assert false | hd::tl ->
let rec start = { data = hd; before = last; after = next }
and couple = lazy (aux (lazy start) hd)
and next = lazy (Lazy.force (fst (Lazy.force couple)))
and last = lazy (Lazy.force (snd (Lazy.force couple)))
and aux before = function
| [] -> (lazy start), before
| hd::tl -> let rec current = lazy { data = hd; before = before; after = after }
and couple = lazy (aux current tl)
and after = lazy (Lazy.force (fst (Lazy.force couple)))
and last = lazy (Lazy.force (snd (Lazy.force couple))) in
current, last
in start
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-09-09 21:15:21