Dlaczego listy wad są powiązane z programowaniem funkcjonalnym?

22

Zauważyłem, że większość języków funkcjonalnych wykorzystuje listę pojedynczo połączoną (listę „wad”) jako najbardziej podstawowe typy list. Przykłady obejmują Common Lisp, Haskell i F #. Różni się to od języków głównego nurtu, w których rodzimymi typami list są tablice.

Dlaczego?

W przypadku Common Lisp (dynamicznie wpisywanego) mam wrażenie, że minusy są na tyle ogólne, że mogą być również podstawą list, drzew itp. To może być mały powód.

Jednak w przypadku języków o typie statycznym nie mogę znaleźć dobrego uzasadnienia, mogę nawet znaleźć kontrargumenty:

  • Funkcjonalny styl zachęca do niezmienności, więc łatwość wstawiania połączonej listy jest mniej korzystna,
  • Funkcjonalny styl zachęca do niezmienności, a więc także do udostępniania danych; tablica jest łatwiejsza do dzielenia się „częściowo” niż lista połączona,
  • Równie dobrze możesz dopasowywać wzorce na zwykłej tablicy, a nawet lepiej (możesz na przykład łatwo spasować od prawej do lewej),
  • Ponadto otrzymasz losowy dostęp za darmo,
  • I (praktyczna zaleta), jeśli język jest wpisany statycznie, możesz zastosować regularny układ pamięci i uzyskać zwiększenie prędkości z pamięci podręcznej.

Dlaczego więc wolisz powiązane listy?

programming-languages functional-programming list linked-list Kos
źródło
4
Biorąc pod uwagę komentarze do odpowiedzi @ sepp2k, myślę, że an array is easier to share "partially" than a linked listnależy wyjaśnić, co masz na myśli. Ze względu na ich rekurencyjny charakter, odwrotnie jest tak, jak rozumiem - możesz częściowo udostępnić połączoną listę, przechodząc przez dowolny węzeł, a tablica musiałaby spędzać czas na tworzeniu nowej kopii. Jeśli chodzi o udostępnianie danych, dwie połączone listy mogą wskazywać ten sam sufiks, co po prostu nie jest możliwe w przypadku tablic.
Izkata
Jeśli tablica definiuje się jako przesunięcie, długość, potrójny bufor, to możesz współdzielić tablicę, tworząc nowy z przesunięciem + 1, długość-1, bufor. Lub mieć specjalny typ tablicy jako podtablicę.
Dobes Vandermeer
@Izkata Mówiąc o tablicach, rzadko mamy na myśli bufor, taki jak wskaźnik na początek ciągłej pamięci w C. Zwykle mamy na myśli jakąś strukturę, która przechowuje długość i wskaźnik na początek owiniętego bufora. W takim systemie operacja krojenia może zwrócić podtablicę, której wskaźnik bufora wskazuje środek bufora (na pierwszy element tablicy podrzędnej), a liczba zliczeń jest taka, że ​​start + count daje ostatni element. Takie operacje krojenia to O (1) w czasie i przestrzeni
Alexander - Przywróć Monikę

Odpowiedzi:

22

Najważniejszym czynnikiem jest to, że możesz przejść do niezmiennej pojedynczo połączonej listy w czasie O (1), co pozwala rekurencyjnie budować listy n-elementów w czasie O (n) w następujący sposób:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

Jeśli zrobiłbyś to przy użyciu niezmiennych tablic, środowisko wykonawcze byłoby kwadratowe, ponieważ każda consoperacja musiałaby skopiować całą tablicę, co prowadziłoby do kwadratowego czasu działania.

Funkcjonalny styl zachęca do niezmienności, a więc także do udostępniania danych; tablica jest łatwiejsza do dzielenia się „częściowo” niż lista z linkami

Zakładam, że przez „częściowe” udostępnianie masz na myśli, że możesz pobrać podtablicę z tablicy w czasie O (1), podczas gdy z połączonymi listami możesz wziąć ogon tylko w czasie O (1) i wszystko inne potrzebuje O (n). To prawda.

Jednak w wielu przypadkach wystarczy wziąć ogon. I musisz wziąć pod uwagę, że możliwość taniego tworzenia podrzędnych nie pomaga, jeśli nie masz możliwości taniego tworzenia tablic. I (bez sprytnych optymalizacji kompilatora) nie ma sposobu, aby tanio budować tablicę krok po kroku.

sepp2k
źródło
To wcale nie jest prawda. Możesz dołączyć do tablic w zamortyzowanym O (1).
DeadMG
10
@DeadMG Tak, ale nie do niezmiennych tablic.
sepp2k
„częściowe udostępnianie” - myślę, że obie listy wad mogą wskazywać na tę samą listę sufiksów (nie wiem, dlaczego tego chcesz) i że możesz przekazać punkt środkowy zamiast początku listy do innej funkcji bez konieczności kopiowania to (robiłem to już wiele razy)
Izkata
@Izkata OP mówił jednak o częściowym udostępnianiu tablic, a nie list. Nigdy też nie słyszałem, że to, co opisujesz, określa się jako częściowe udostępnianie. To tylko udostępnianie.
sepp2k
1
@Izkata OP używa terminu „tablica” dokładnie trzy razy. Kiedyś powiedzieć, że języki FP używają połączonych list, podczas gdy inne języki używają tablic. Raz powiedzą, że tablice lepiej współdzielą częściowo niż listy połączone, a raz powiedzą, że tablice można równie dobrze dopasować do wzorca (jako listy połączone). We wszystkich przypadkach kontrastuje tablice i listy połączone (aby podkreślić, że tablice byłyby bardziej przydatne jako podstawowa struktura danych niż listy połączone, co prowadzi do pytania, dlaczego listy połączone są preferowane w FP), więc nie rozumiem, jak on może używać terminów zamiennie.
sepp2k
4

Myślę, że sprowadza się to do łatwej implementacji list w kodzie funkcjonalnym.

Schemat:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

data  [a]  =  [] | a : [a]

Tablice są trudniejsze i nie są tak ładne do wdrożenia. Jeśli chcesz, aby były wyjątkowo szybkie, będą musiały być napisane niskim poziomem.

Dodatkowo rekurencja działa znacznie lepiej na listach niż na tablicach. Zastanów się, ile razy rekurencyjnie korzystałeś / generowałeś listę w porównaniu do zindeksowanej tablicy.

Pubby
źródło
Nie powiedziałbym, że nazywanie wersji schematu implementacją list połączonych jest poprawne. Nie będziesz mógł używać go do przechowywania niczego poza funkcjami. Również tablice są trudniejsze (w rzeczywistości niemożliwe) do implementacji w dowolnym języku, który nie ma wbudowanej obsługi (lub fragmentów pamięci), podczas gdy listy połączone wymagają tylko czegoś takiego jak struktury, klasy, rekordy lub algebraiczne typy danych do wdrożenia. To nie jest specyficzne dla funkcjonalnych języków programowania.
sepp2k
@ sepp2k Co masz na myśli mówiąc „przechowuj wszystko oprócz funkcji” ?
Pubby
1
Miałem na myśli to, że zdefiniowane w ten sposób listy nie mogą przechowywać niczego, co nie jest funkcją. To jednak nie jest prawda. Nie wiem, dlaczego tak myślałem. Przepraszam za to.
sepp2k
2

Pojedynczo połączona lista jest najprostszą trwałą strukturą danych .

Trwałe struktury danych są niezbędne do wydajnego, czysto funkcjonalnego programowania.

ziggystar
źródło
1
to wydaje się jedynie powtórzyć punkt wykonany i wyjaśnione w górę odpowiedź , która została wysłana ponad 4 lat temu
komara
3
@gnat: Najlepsza odpowiedź nie wspomina o trwałych strukturach danych lub o tym, że pojedynczo połączone listy są najprostszą trwałą strukturą danych lub że są niezbędne dla wydajnego programowania o czysto funkcjonalnym charakterze. Nie mogę w żaden sposób pokrywać się z najlepszą odpowiedzią.
Michael Shaw,
2

Możesz łatwo korzystać z węzłów Cons tylko wtedy, gdy masz język odśmiecania.

Węzły Cons mają wiele wspólnego z funkcjonalnym stylem programowania wywołań rekurencyjnych i niezmiennymi wartościami. Więc pasuje dobrze do modelu programisty umysłowego.

I nie zapomnij o przyczynach historycznych. Dlaczego nadal są nazywane węzłami Cons, a co gorsza nadal używają car i cdr jako akcesoriów? Ludzie uczą się z podręczników i kursów, a następnie z nich korzystają.

Masz rację, w prawdziwym świecie tablice są znacznie łatwiejsze w użyciu, zajmują tylko połowę miejsca w pamięci i są znacznie wydajniejsze ze względu na brak poziomu pamięci podręcznej. Nie ma powodu, aby używać ich w imperatywnych językach.

Lothar
źródło
1

Listy połączone są ważne z następującego powodu:

Po wybraniu liczby takiej jak 3 i przekonwertowaniu jej na następną, taką jak succ(succ(succ(zero))), a następnie skorzystaj z podstawienia za pomocą {succ=List node with some memory space}, a {zero = end of list}skończysz z połączoną listą (o długości 3).

Rzeczywistą ważną częścią są liczby, podstawienia, przestrzeń pamięci i zero.

tp1
źródło