Dlaczego listy są wybraną strukturą danych w językach funkcjonalnych?

Większość języków funkcjonalnych używa list połączonych jako podstawowej niezmiennej struktury danych. Dlaczego listy, a nie np. Drzewa? Drzewa mogą również ponownie wykorzystywać ścieżki, a nawet listy modeli.

functional-programming Filip Haglund
źródło

Możliwy duplikat Dlaczego listy wad są powiązane z programowaniem funkcjonalnym?

komara

@gnat - to nie jest duplikat tego pytania. Przyjęta i poprawna odpowiedź na to pytanie jest zasadniczo „ponieważ niezmienna połączona lista pozwala na dzielenie ogonów między listami uaktualnionymi i oryginalnymi”, odpowiedź wskazana jako część kontekstu tego pytania ...

Jules,

Należy wyjaśnić, że „lista” (abstrakcyjna koncepcja programowania) różni się od „listy powiązanej” (szczególna implementacja tej koncepcji), podobnie jak specyfikacja języka programowania różni się od jego implementacji. Pytanie „dlaczego języki funkcjonalne używają list (koncepcji programowania abstrakcyjnego) jako głównej struktury danych?” jest subtelnie, ale zasadniczo bardzo różni się od pytania „dlaczego wspólne implementacje języków funkcjonalnych X, Y i Z używają połączonych list jako głównej struktury danych?”

I scala Vector (który jest zaimplementowany jako drzewo) jest nieco bardziej preferowany niż Lista stackoverflow.com/questions/6928327/... W praktyce większość osób nadal korzysta z List (z tego, co widziałem).

Akavall,

Zrobiłem kilka kursów programowania funkcjonalnego w Scali i korzystałem dużo z drzew. Po prostu lista jest prostsza dla przykładów. Drzewa są używane do problemów z wydajnością. Możesz tworzyć drzewa niewymienne, ponownie wykorzystując część starszych drzew, tak jak dodajesz elementy do niewymiennych list.

Borjab

Odpowiedzi:

Ponieważ listy są prostsze niż drzewa. (Widać to trywialnie dzięki temu, że lista jest zdegenerowanym drzewem, w którym każdy węzeł ma tylko jedno dziecko.)

Lista wad to najprostsza możliwa rekurencyjna struktura danych o dowolnym rozmiarze.

Guy Steele argumentował podczas projektowania języka programowania Fortress, że w przypadku masowo równoległych obliczeń przyszłości, zarówno nasze struktury danych, jak i nasz przepływ sterowania powinny mieć kształt drzewa z wieloma gałęziami, a nie liniowymi, jak są teraz. Ale na razie większość naszych podstawowych bibliotek struktur danych została zaprojektowana z myślą o przetwarzaniu sekwencyjnym, iteracyjnym (lub rekurencyjnym), a nie przetwarzaniu równoległym.

Należy pamiętać, że na przykład w Clojure, której dane struktury zostały zaprojektowane specjalnie dla równoległego, rozproszonego, „mętny” dzisiejszego świata, a nawet tablice (zwane wektory w Clojure), prawdopodobnie najbardziej „liniowy” struktury danych z nich wszystkich, są faktycznie realizowane jako drzewa.

Krótko mówiąc: lista wad to najprostsza możliwa stała struktura danych rekurencyjnych i nie było potrzeby wybierania bardziej skomplikowanego „domyślnego”. Inne są oczywiście dostępne jako opcje, np. Haskell ma tablice, kolejki priorytetowe, mapy, stosy, pułapki, próby i wszystko, co można sobie wyobrazić, ale domyślnie jest to prosta lista wad.

Jörg W Mittag
źródło

Tak, wektory Clojure są implementowane jako drzewa - ale należy zauważyć, że są to próby odwzorowane w tablicy skrótów , a nie standardowe pliki binarne data Tree a = Leaf a | Branch a (Tree a) (Tree a). To wzmacnia twój argument „prostoty”.

wchargin

Trwałe wektory FWIW Clojure są implementowane jako (jak @wchargin wskazuje na dość złożone) drzewa w celu szybkiego (logarytmicznego z dużą bazą) dostępu i aktualizacji dowolnych elementów, nie do samej pracy równoległej per se (część niezmienna zajmuje się tym niektórym stopień). Inne języki FP dokonują tego samego wyboru (czasem z różnymi rodzajami drzew), kiedy chcą obu z nich (np. Haskella Sequencelub Scali Vector), ale nie używają drzew, gdy potrzebują tylko czytać, ponieważ mogą to osiągnąć w czasie rzeczywistym (np. Haskell's Vectorlub F # via .Net's ImmutableArray)

badcook

Np. pmapPingowanie nad wektorem w Clojure nadal uzyskuje dostęp do każdego elementu sekwencyjnie; struktura drzewa wektora jest na ogół ukryta przed użytkownikiem końcowym.

badcook

W rzeczywistości te listy to drzewa! Masz węzły z dwoma polami cari cdr, które mogą zawierać więcej takich węzłów lub liści. Jedyną rzeczą, która sprawia, że te drzewa na listach, jest konwencja, aby zinterpretować ten cdrlink jako link do następnego węzła na liście liniowej, a carlink jako wartość bieżącego węzła.

To powiedziawszy, myślę, że przewaga połączonych list w programowaniu funkcjonalnym jest związana z przewagą rekurencji po iteracji. Gdy jedynym dostępnym zapętlonym konstruktem jest rekursja (ogona), potrzebujesz struktur danych, które są z tym łatwe w użyciu; i połączone listy są do tego idealne.

cmaster
źródło

to zależy od języka. Jasne, możesz zaimplementować drzewo w LISP-ach, używając komórek przeciw, ale na przykład w Haskell będziesz potrzebować zupełnie osobnej struktury. Zauważ też, że większość języków funkcjonalnych ma znacznie więcej zapętlonych konstrukcji niż rekurencja ogona. Biblioteki podstawowe Haskell zapewniają na przykład fałdy (lewy i prawy), skanowanie, przechodzenie nad drzewami, iteracje nad kluczami i wartościami map oraz wiele innych bardziej specjalistycznych struktur. Jasne, są one realizowane za pomocą rekurencji za kulisami, ale użytkownik nie musi nawet o tym myśleć, aby działały.

Jules

@Jules Niemniej jednak funkcjonalne programowanie zostało opracowane i było pod dużym wpływem języków takich jak LISP. Oczywiście możliwe jest usprawnienie całej tej iteracji listy za pomocą tablic pod maską lub dodanie cukru syntaktycznego, który ukrywa charakter listy, ale czyste programowanie funkcjonalne może zrobić to i bez niej. Ponadto Haskell to całkiem nowy język (32 lata młodszy od LISP), który dodaje całkiem sporo innych pomysłów, cukru syntaktycznego itp. Do czystego funkcjonalnego stylu. Myślę, że ocenianie programowania funkcjonalnego na podstawie oceny Haskella przypomina trochę ocenianie mikserów na podstawie oceny

thermomix

@cmaster, podczas gdy Haskell jest młodszy, ma jeszcze 27 lat i wpływał na wiele języków (w tym Python, Java i C #, aby wymienić tylko kilka wpływowych). Ocenianie programowania funkcjonalnego przez LISP jest jak ocenianie programowania imperatywnego przez ALGOL - oba przeszły długą drogę, zanim stały się nierozpoznawalne. DOBRZE. Lisp jest prawdopodobnie nadal aktualny, ale nie uznałbym go za „główny nurt” i brakuje mu wielu późniejszych informacji, w tym rodzajów ML.

Maciej Piechotka,

Nie możesz przetwarzać pojedynczo połączonych ogonów rekurencyjnie lub iteracyjnie bez wyraźnego stosu, jeśli chcesz dotknąć całego drzewa, więc nie sądzę, aby rekurencja ogona miała z tym coś wspólnego.

k_g

@MaciejPiechotka Ani Python, Java, ani C # nie mogą być postrzegane jako języki funkcjonalne, są niezbędne i dodają kilka funkcji inspirowanych programowaniem funkcjonalnym. Po zmianie stanu jesteś mocno w obszarze imperatywnego, niefunkcjonalnego programowania. Zgadzam się jednak z tobą, że LISP zdecydowanie nie jest głównym nurtem.

cmaster