Listy Rocka

Zdecydowanie najbardziej przyjazna struktura danych dla sekwencyjnych danych w Haskell jest lista

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

Listy dają Θ(1) minusy i dopasowanie wzorca. Biblioteka standardowa, a co za tym idzie preludium, jest pełna przydatnych funkcji listowych, które powinny zaśmiecać Twój kod (foldr,map,filter). Listy są trwałe , aka czysto funkcjonalne, co jest bardzo miłe. Listy Haskella nie są tak naprawdę "listami", ponieważ są coinductive (inne języki nazywają te strumienie) więc rzeczy takie jak

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

Pracuj wspaniale. Nieskończone struktury danych rock.

Listy w Haskell zapewniają interfejs podobny do iteratorów w językach imperatywnych (z powodu lenistwa). Ma więc sens, że są one szeroko stosowane.

Z drugiej strony

Pierwszy problem z listami polega na tym, że indeksowanie do nich (!!) zajmuje Θ(k) czas, co jest denerwujące. Ponadto dodawanie może być powolne ++, ale leniwy model oceny Haskella oznacza, że mogą one być traktowane jako w pełni amortyzowane, jeśli w ogóle się zdarzają.

Drugi problem z listami polega na tym, że mają słabą lokalizację danych. Prawdziwe procesory mają wysokie stałe, gdy obiekty w pamięci nie są ułożone obok siebie. Tak więc, w C++ std::vector ma szybszy "snoc" (umieszczanie obiektów na końcu) niż jakakolwiek czysta struktura danych linked list, którą znam, chociaż nie jest to trwała struktura danych tak mniej przyjazna niż listy Haskella.

Trzeci problem z listami polega na tym, że mają słaba wydajność przestrzeni. Pakiety dodatkowych wskaźników zwiększają pamięć (o stały współczynnik).

Sekwencje Są Funkcjonalne

Data.Sequence jest wewnętrznie oparty na palcach drzew (wiem, nie chcesz tego wiedzieć), co oznacza, że mają ładne właściwości

1. czysto funkcjonalne. Data.Sequence jest w pełni trwałą strukturą danych.
2. cholernie szybki dostęp do początku i końca drzewa. Θ(1) (amortyzowany), aby uzyskać pierwszy lub ostatni element, lub aby dołączaj drzewa. Na liście rzeczy są najszybsze, Data.Sequence jest co najwyżej stałą wolniejszą.
3. Θ (log n) dostęp do środka sekwencji. Obejmuje to wstawianie wartości do tworzenia nowych sekwencji
4. wysokiej jakości API

Z drugiej strony, Data.Sequence nie robi zbyt wiele dla problemu lokalizacji danych i działa tylko dla zbiorów skończonych (jest mniej leniwy niż listy)

Tablice nie są dla słabego serca

Tablice są jednym z najważniejszych danych struktury w CS, ale nie pasują zbyt dobrze do leniwego, czystego świata funkcjonalnego. Tablice zapewniają Θ(1) dostęp do środka zbioru i wyjątkowo dobrą lokalizację danych/czynniki stałe. Ale ponieważ nie pasują bardzo dobrze do Haskell, są trudne do użycia. Aktualnie istnieje wiele różnych typów tablic w bieżącej bibliotece standardowej. Należą do nich tablice w pełni trwałe, tablice mutable dla IO monad, tablice mutable dla ST monad i wersje un-boxed powyżej. Aby dowiedzieć się więcej, sprawdź Haskell wiki

Wektor jest" lepszą " tablicą

Pakiet Data.Vector dostarcza wszystkie dobroci tablicy, w wyższym poziomie i czystszym API. Jeśli naprawdę nie wiesz, co robisz, powinieneś ich użyć, jeśli potrzebujesz array like performance. Oczywiście nadal obowiązują pewne zastrzeżenia-zmienne tablice, takie jak struktury danych, po prostu nie grają ładnie w czystych leniwych językach. Mimo to, czasami chcesz, że o (1) performance, i Data.Vector daje go do Ciebie w przydatna paczka.

Masz inne opcje

Jeśli chcesz tylko listy z możliwością efektywnego wstawiania na końcu, możesz użyć listy różnic . Najlepszym przykładem wykonania listy jest [Char], które preludium zostało nazwane String. Char listy są wygodne, ale zwykle działają w kolejności 20 razy wolniej niż ciągi C, więc możesz używać Data.Text lub bardzo szybkiego Data.ByteString. Jestem pewien, że są inne sekwencje zorientowane biblioteki, o których teraz nie myślę.

Podsumowanie

90+% czasu potrzebuję sekwencyjnego zbierania w listach Haskella to właściwa struktura danych. Listy są jak Iteratory, funkcje, które zużywają listy, mogą być łatwo używane z dowolną z tych innych struktur danych za pomocą funkcji toList, które są dołączone. W lepszym świecie preludium byłoby w pełni parametryczne co do tego, jakiego typu kontenera używa, ale obecnie [] MIOTA standardową bibliotekę. Tak więc, używając list (prawie) każde miejsce jest zdecydowanie w porządku.
Można uzyskać w pełni parametryczne wersje większości funkcji listy (i są one szlachetne do ich użycia)

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

W rzeczywistości, Data.Traversable definiuje API, które jest mniej lub bardziej uniwersalne dla każdej rzeczy "list like".

Mimo że można być dobrym i pisać tylko w pełni parametryczny kod, większość z nas nie jest i używa listy wszędzie. Jeśli się uczysz, zdecydowanie sugeruję ci to zrobić.

---

EDIT: na podstawie komentarzy I zdaj sobie sprawę, że nigdy nie wyjaśniłem, kiedy używać Data.Vector vs Data.Sequence. Tablice i Wektory zapewniają niezwykle szybkie operacje indeksowania i wycinania, ale są zasadniczo przejściowymi (imperatywnymi) strukturami danych. Czyste funkcjonalne struktury danych, takie jak Data.Sequence i [], pozwalają efektywnie produkować nowe wartości ze starych wartości, tak jakbyś zmodyfikował stare wartości.

  newList oldList = 7 : drop 5 oldList

Nie modyfikuje starej listy i nie musi jej kopiować. Więc nawet jeśli oldList jest niewiarygodnie długa, ta "modyfikacja" będzie bardzo szybko. Podobnie

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

Wytworzy nową sekwencję z newValue DLA w miejsce jej elementu 3000. Ponownie, nie niszczy starej sekwencji, tylko tworzy nową. Ale robi to bardzo efektywnie, biorąc O(log(min (k,k-n)) gdzie n jest długością ciągu, A k indeksem, który modyfikujesz.

Nie można tego łatwo zrobić z Vectors i Arrays. Mogą być zmodyfikowane ale jest to prawdziwa imperatywna modyfikacja, więc nie można tego zrobić w regularnych Kod Haskella. Oznacza to, że operacje w Vector, które dokonują modyfikacji, takich jak snoc i cons, muszą skopiować cały wektor, więc zająć O(n) czas. Jedynym wyjątkiem od tego jest to, że możesz użyć mutowalnej wersji (Vector.Mutable) Wewnątrz ST monady (lub IO) i wykonywać wszystkie swoje modyfikacje tak, jak w imperatywnym języku. Kiedy skończysz, "zamrażasz" swój wektor, aby przekształcić się w niezmienną strukturę, której chcesz użyć z czystym kodem.

Moje uczucie jest takie, że jeśli lista nie jest odpowiednia, domyślnie należy użyć Data.Sequence. Używaj Data.Vector tylko wtedy, gdy twój schemat użytkowania nie wymaga wprowadzania wielu modyfikacji lub jeśli potrzebujesz ekstremalnie wysokiej wydajności w ST / IO monads.

Jeśli całe to gadanie o monadzie ST sprawia, że jesteś zdezorientowany: tym bardziej powód, aby trzymać się czystego, szybkiego i pięknego Data.Sequence.