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.