Podwójnie połączona lista ma minimalny narzut (tylko kolejny wskaźnik na komórkę) i pozwala na dołączanie do obu końców i przechodzenie tam i z powrotem i ogólnie daje dużo zabawy.

Cóż, jeśli spojrzysz nieco głębiej, obie faktycznie zawierają również tablice w języku podstawowym:

• Piąty poprawiony raport programu (R5RS) obejmuje typ wektora , który jest zbiorem indeksowanym liczbami całkowitymi o stałej wielkości z czasem lepszym niż liniowy dla dostępu losowego.
• Raport Haskell 98 ma również typ tablicy .

Jednak instrukcja programowania funkcjonalnego od dawna kładzie nacisk na listy z pojedynczymi linkami zamiast z tablic lub list z podwójnymi linkami. Prawdopodobnie przeceniony. Jest jednak kilka powodów.

Po pierwsze, listy z pojedynczym połączeniem są jednym z najprostszych, a jednocześnie najbardziej przydatnych typów danych rekurencyjnych. Zdefiniowany przez użytkownika odpowiednik typu listy Haskell można zdefiniować w następujący sposób:

data List a           -- A list with element type `a`...
  = Empty             -- is either the empty list...
  | Cell a (List a)   -- or a pair with an `a` and the rest of the list. 

Fakt, że listy są rekurencyjnym typem danych, oznacza, że ​​funkcje działające na listach zwykle używają rekurencji strukturalnej . W kategoriach Haskell: dopasowujesz wzorce do konstruktorów listy i powtarzasz się w podsekcji listy. W tych dwóch podstawowych definicjach funkcji używam zmiennej, asaby odwoływać się do końca listy. Zauważ więc, że rekurencyjne wywołania „schodzą” w dół listy:

map :: (a -> b) -> List a -> List b
map f Empty = Empty
map f (Cell a as) = Cell (f a) (map f as)

filter :: (a -> Bool) -> List a -> List a
filter p Empty = Empty
filter p (Cell a as)
    | p a = Cell a (filter p as)
    | otherwise = filter p as

Ta technika gwarantuje, że twoja funkcja zostanie zakończona dla wszystkich skończonych list, a także jest dobrą techniką rozwiązywania problemów - ma tendencję do naturalnego dzielenia problemów na prostsze, bardziej wytrzymałe części.

Tak więc listy z pojedynczym połączeniem są prawdopodobnie najlepszym typem danych do wprowadzenia studentów w te techniki, które są bardzo ważne w programowaniu funkcjonalnym.

Drugi powód to nie tyle powód „dlaczego pojedynczo połączonych list”, ale raczej powód „dlaczego podwójnie połączonych list lub tablic”: te ostatnie typy danych często wymagają mutacji (zmienne modyfikowalne), które programowanie funkcjonalne bardzo często ucieka od. Tak się składa:

• W chętnym języku, takim jak Scheme, nie można utworzyć podwójnie połączonej listy bez użycia mutacji.
• W leniwym języku, takim jak Haskell, możesz utworzyć podwójnie połączoną listę bez użycia mutacji. Ale ilekroć utworzysz nową listę na podstawie tej, będziesz zmuszony skopiować większość, jeśli nie całą strukturę oryginału. Podczas gdy w przypadku list z pojedynczym połączeniem możesz pisać funkcje korzystające z „współdzielenia struktury” - nowe listy mogą w razie potrzeby ponownie wykorzystywać komórki starych list.
• Tradycyjnie, jeśli używałeś tablic w niezmienny sposób, oznaczało to, że za każdym razem, gdy chciałeś zmodyfikować tablicę, musiałeś skopiować całość. ( vectorJednak ostatnie biblioteki Haskell, takie jak , znalazły techniki, które znacznie poprawiły ten problem).

Trzeci i ostatni powód dotyczy przede wszystkim leniwych języków, takich jak Haskell: leniwe listy z pojedynczymi linkami w praktyce są często bardziej podobne do iteratorów niż do list w pamięci. Jeśli Twój kod zużywa elementy listy sekwencyjnie i wyrzuca je w trakcie pracy, kod obiektowy zmaterializuje komórki listy i jej zawartość tylko w miarę przechodzenia przez listę.

Oznacza to, że cała lista nie musi istnieć jednocześnie w pamięci, tylko bieżąca komórka. Komórki przed bieżącą można zbierać w pamięci (co nie byłoby możliwe przy podwójnie połączonej liście); komórki później niż bieżąca nie muszą być obliczane, dopóki się tam nie dostaniesz.

To idzie nawet dalej. W kilku popularnych bibliotekach Haskell zastosowano technikę zwaną fusion , w której kompilator analizuje kod przetwarzania list i wykrywa listy pośrednie, które są generowane i konsumowane kolejno, a następnie „wyrzucane”. Dzięki tej wiedzy kompilator może całkowicie wyeliminować przydział pamięci komórek tych list. Oznacza to, że pojedyncza lista w programie źródłowym Haskell, po kompilacji, może zostać przekształcona w pętlę zamiast w strukturę danych.

Fuzja jest także techniką stosowaną przez wspomnianą vectorbibliotekę do generowania wydajnego kodu dla niezmiennych tablic. To samo dotyczy niezwykle popularnych bytestring(tablice bajtowe) i text(ciągów znaków Unicode), które zostały zbudowane jako zamiennik niezbyt wspaniałego rodzimego Stringtypu Haskell (który jest taki sam, jak [Char]pojedyncza lista znaków). Tak więc we współczesnym Haskell istnieje trend, w którym niezmienne typy macierzy z obsługą fuzji stają się bardzo popularne.

Łączenie list ułatwia fakt, że na liście z pojedynczym połączeniem możesz iść do przodu, ale nigdy do tyłu . Powoduje to bardzo ważny temat w programowaniu funkcjonalnym: używanie „kształtu” typu danych w celu uzyskania „kształtu” obliczenia. Jeśli chcesz przetwarzać elementy sekwencyjnie, lista z pojedynczym połączeniem jest typem danych, który, gdy użyjesz go z rekurencją strukturalną, daje ci ten wzorzec dostępu bardzo naturalnie. Jeśli chcesz zastosować strategię „dziel i rządź”, aby zaatakować problem, struktury danych drzewa zwykle obsługują to bardzo dobrze.

Wiele osób wcześnie rezygnuje z funkcjonalnego wagonu programistycznego, więc uzyskują one dostęp do list z pojedynczymi linkami, ale nie do bardziej zaawansowanych pomysłów.

Ponieważ działają dobrze z niezmiennością. Załóżmy, że masz dwie niezmienne listy [1, 2, 3]i [10, 2, 3]. Reprezentowane jako pojedynczo połączone listy, w których każdy element na liście jest węzłem zawierającym element i wskaźnik do reszty listy, wyglądałyby następująco:

node -> node -> node -> empty
 1       2       3

node -> node -> node -> empty
 10       2       3

Widzisz, jak [2, 3]porcje są identyczne? Ze zmiennymi strukturami danych są to dwie różne listy, ponieważ kod zapisujący nowe dane na jednej z nich nie musi wpływać na kod przy użyciu drugiej. Jednak przy niezmiennych danych wiemy, że zawartość list nigdy się nie zmieni i kod nie może zapisać nowych danych. Możemy więc ponownie użyć ogonów i sprawić, by dwie listy miały część swojej struktury:

node -> node -> node -> empty
 1      ^ 2       3
        |
node ---+
 10

Ponieważ kod korzystający z dwóch list nigdy ich nie zmutuje, nigdy nie musimy się martwić o zmiany jednej listy wpływające na drugą. Oznacza to również, że dodając element na początku listy, nie musisz kopiować i tworzyć zupełnie nowej listy.

Jeśli jednak spróbujesz reprezentować [1, 2, 3]i [10, 2, 3]jako podwójnie połączone listy:

node <-> node <-> node <-> empty
 1       2       3

node <-> node <-> node <-> empty
 10       2       3

Teraz ogony nie są już identyczne. Pierwszy [2, 3]ma wskaźnik 1na głowie, ale drugi ma wskaźnik na 10. Dodatkowo, jeśli chcesz dodać nowy element do nagłówka listy, musisz zmutować poprzedni nagłówek listy, aby wskazywał na nowy nagłówek.

Problem wielu głowic może potencjalnie zostać rozwiązany przez to, że każdy węzeł przechowuje listę znanych głowic i tworzenie nowych list modyfikuje to, ale następnie musisz pracować nad utrzymaniem tej listy w cyklach odśmiecania, gdy wersje listy z różnymi głowicami mają różne czasy życia, ponieważ są używane w różnych fragmentach kodu. Dodaje złożoności i kosztów ogólnych, a przez większość czasu nie jest tego warte.

Odpowiedź @ sacundim jest w większości prawdą, ale istnieją również inne ważne spostrzeżenia na temat kompromisów dotyczących projektów językowych i wymagań praktycznych.

Obiekty i odniesienia

Języki te zwykle mandat (lub zakładać) obiekty posiadające niezwiązane zakresów dynamicznych (lub w języku C w żargonie, całe życie , choć nie dokładnie to samo ze względu na różnice w rozumieniu obiektów spośród tych języków, patrz niżej) domyślnie, unikając odniesień pierwszej klasy ( np. wskaźniki obiektów w C) i nieprzewidziane zachowanie w regułach semantycznych (np. niezdefiniowane zachowanie ISO C dotyczące semantyki).

Ponadto pojęcie obiektów (pierwszej klasy) w takich językach jest konserwatywnie restrykcyjne: domyślnie nie są określone żadne właściwości „lokalizacyjne” i gwarantowane. Jest to zupełnie inne w niektórych językach podobnych do ALGOL, których obiekty nie mają niezwiązanych zakresów dynamicznych (np. W C i C ++), w których obiekty zasadniczo oznaczają pewne rodzaje „typowanego magazynu”, zwykle w połączeniu z lokalizacjami pamięci.

Kodowanie pamięci w obiektach ma pewne dodatkowe zalety, takie jak możliwość dołączania deterministycznych efektów obliczeniowych przez cały okres ich życia, ale jest to inny temat.

Problemy symulacji struktur danych

Bez referencji najwyższej klasy pojedynczo połączone listy nie mogą skutecznie i przenośnie symulować wielu tradycyjnych (chętnych / modyfikowalnych) struktur danych, ze względu na naturę reprezentacji tych struktur danych i ograniczone prymitywne operacje w tych językach. (Wręcz przeciwnie, w C można dość łatwo wyprowadzić połączone listy nawet w ściśle zgodnym programie ). Takie alternatywne struktury danych, takie jak tablice / wektory, mają pewne lepsze właściwości w porównaniu do pojedynczo połączonych list w praktyce. Właśnie dlatego R ⁵ RS wprowadza nowe prymitywne operacje.

Istnieją jednak różnice między typami wektorów / tablic a listami podwójnie połączonymi. Często przyjmuje się, że tablica ma złożoność czasu dostępu O (1) i mniejszy narzut miejsca, które są doskonałymi właściwościami niepodzielonymi przez listy. (Chociaż ściśle mówiąc, żadna z nich nie jest gwarantowana przez ISO C, ale użytkownicy prawie zawsze tego oczekują i żadna praktyczna implementacja nie naruszyłaby tych dorozumianych gwarancji zbyt wyraźnie.) OTOH, podwójnie połączona lista często powoduje, że obie właściwości są jeszcze gorsze niż lista pojedynczo połączona , podczas gdy iteracja do tyłu / do przodu jest również obsługiwana przez tablicę lub wektor (wraz z indeksami liczb całkowitych) z jeszcze mniejszym narzutem. Dlatego podwójnie połączona lista nie działa ogólnie lepiej. Jeszcze gorzej, wydajność w zakresie wydajności pamięci podręcznej i opóźnienia w dynamicznym przydzielaniu pamięci listom jest katastrofalnie gorsza niż wydajność dla tablic / wektorów, gdy używany jest domyślny alokator zapewniany przez podstawowe środowisko implementacyjne (np. libc). Zatem bez bardzo specyficznego i „sprytnego” środowiska uruchomieniowego, które mocno optymalizuje takie tworzenie obiektów, typy tablic / wektorów są często preferowane od list połączonych. (Na przykład przy użyciu ISO C ++ istnieje pewne zastrzeżeniestd::vectorpowinien być preferowany niż std::listdomyślnie.) Zatem wprowadzenie nowych prymitywów do konkretnej obsługi (podwójnie) połączonych list zdecydowanie nie jest tak korzystne, jak w praktyce obsługa struktur tablic / wektorów.

Szczerze mówiąc, listy nadal mają pewne określone właściwości lepsze niż tablice / wektory:

• Listy są oparte na węzłach. Usunięcie elementów z list nie unieważnia odwołania do innych elementów w innych węzłach. (Dotyczy to również niektórych struktur danych drzewa lub wykresu.) OTOH, tablice / wektory mogą zawierać odniesienia do unieważnienia pozycji końcowej (w niektórych przypadkach z masywną realokacją).
• Listy mogą się dzielić w czasie O (1). Rekonstrukcja nowych tablic / wektorów z obecnymi jest znacznie bardziej kosztowna.

Jednak te właściwości nie są zbyt ważne dla języka z wbudowaną obsługą list połączonych pojedynczo, który jest już zdolny do takiego użycia. Mimo że nadal istnieją różnice, w językach z obowiązkowym dynamicznym zakresem obiektów (co zwykle oznacza, że ​​kolektor śmieci ukrywa wiszące odwołania), unieważnienie może być również mniej ważne, w zależności od intencji. Tak więc jedynymi przypadkami, w których wygrywają podwójnie połączone listy, mogą być:

• Potrzebne są zarówno gwarancja nieprzydzielenia, jak i dwukierunkowa iteracja. (Jeśli wydajność dostępu do elementów jest ważna, a zestaw danych jest wystarczająco duży, wybrałbym zamiast tego drzewa wyszukiwania binarnego lub tabele skrótów).
• Potrzebne są wydajne operacje łączenia dwukierunkowego. Jest to dość rzadkie. (Spełniam tylko wymagania dotyczące implementacji czegoś takiego jak rekordy historii liniowej w przeglądarce).

Niezmienność i aliasing

W czystym języku, takim jak Haskell, obiekty są niezmienne. Obiekt schematu jest często używany bez mutacji. Taki fakt umożliwia skuteczne zwiększenie wydajności pamięci dzięki internowaniu obiektów - niejawne współużytkowanie wielu obiektów o tej samej wartości w locie.

Jest to agresywna strategia optymalizacji wysokiego poziomu w projektowaniu języka. Wiąże się to jednak z problemami z wdrożeniem. W rzeczywistości wprowadza ukryte aliasy do podstawowych komórek pamięci. Utrudnia to analizę aliasingu. W rezultacie może być prawdopodobnie mniej możliwości wyeliminowania narzutu referencji innych niż najlepsze, nawet użytkownicy nigdy ich nie dotykają. W językach takich jak Scheme, gdy mutacja nie zostanie całkowicie wykluczona, zaburza to również paralelizm. Jednak może być OK w leniwym języku (który i tak już ma problemy z wydajnością spowodowane przez thunks).

W przypadku programowania ogólnego przeznaczenia taki wybór projektu języka może być problematyczny. Jednak niektóre popularne wzorce kodowania funkcjonalnego sprawiają, że języki nadal działają dobrze.