Wewnętrzna reprezentacja list Haskella?

Haskell obsługuje podstawowe operacje na listach, takich jak head, tail, init i last. Zastanawiam się wewnętrznie, w jaki sposób Haskell reprezentuje swoje dane na liście? Jeśli jest to lista pojedynczo połączona, operacje mogą stać się kosztowne w miarę wzrostu listy. Jeśli jest to lista podwójnie powiązana, wszystkie cztery operacje mogą być wykonane dość łatwo, aczkolwiek kosztem jakiejś pamięci. Tak czy inaczej, ważne jest, aby wiedzieć, więc mogę napisać odpowiedni kod. (choć etos programowania funkcjonalnego wydaje się być jednym z "zapytaj, co robi, a nie jak to robi").Wewnętrzna reprezentacja list Haskella?

Źródło

2013-02-25 limp_chimp

"zapytaj, co robi, a nie jak to robi" Nie, jeśli martwisz się pisaniem kodu, który jest dość szybki;) –

Cóż, tak właśnie myślę :-) Stąd moje pytanie. –

"Jeśli jest to lista podwójnie powiązana, wszystkie cztery operacje mogą być wykonane O (1) dość łatwo" w rzeczywistości, nie jest łatwo, jeśli chcesz pozostać czysto funkcjonalnym, więc zwykłe listy podwójnie powiązane nie są używane w Haskell . Wykonywanie wszystkiego w _O_ (1), pozostając czysto funkcjonalnym, wymaga raczej bardziej wyrafinowanych struktur danych - jednak okazuje się, że wykorzystując lenistwo Haskella, możesz osiągnąć znacznie więcej dzięki operacjom _O_ (1) (lub w jakiś sposób amortyzowanym _O_ (_n_), która jest prawie tak dobra) na swoich pojedynczo powiązanych połączonych listach, niż byłoby to możliwe w każdym języku proceduralnym. – leftaroundabout

Listy są reprezentowane jako ... pojedynczo połączone listy. Definicja jest dana przez:

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

który można napisać jako:

data List a = Empty | Cons a (List a)

Układ pamięci jest całkowicie określony przez to.

Konstruktorzy są sterty przydzielone
wewnętrzne pola polimorficzne są wskaźnikami do innych przydzielonych węzłów
Kręgosłup jest leniwy

więc skończyć z czymś takim:

enter image description here

Tak head jest O (1) na tej strukturze, podczas last lub (++) jest O (n)

Nie ma magicznej do struktur danych w Haskell - ich prosta definicja sprawia, że do końca jasne, co złożoność będzie (modulo lenistwo). Jeśli potrzebujesz innej złożoności, użyj innej struktury (takiej jak IntMap, Sequence, HashMap, Vector itd.) ...

Źródło

2013-02-25 08:51:56

Dzięki za odpowiedź.Nie jestem pewna, czy konieczne jest podkreślenie, jak jasna/oczywista powinna być ta odpowiedź - jestem początkującym dla Haskella, a pochodząc z C to ogromna zmiana, więc wciąż zastanawiam się nad tym. W każdym razie dzięki jeszcze raz. –

Och, nie mam na myśli tego "łatwego", tylko że nie ma w tym magii. Jeśli spojrzysz tylko na definicję typu danych, wszystko można uzyskać. –

Dwa duże zastrzeżenia: ** lenistwo ** i ** fuzja **. Lenistwo oznacza, że na przykład w 'xs ++ ys' płacisz tylko za dopłatę w takim stopniu, w jakim poruszasz się po liście wyników; 'head (xs ++ ys)' to O (1), a nie O (n). Fusion oznacza, że wiele operacji nie wiąże się z dodatkowymi kosztami w porównaniu z operacjami przejścia; na przykład 'map (* 2) (xs ++ ys)' kosztuje mniej niż suma kosztów 'map (* 2)' i '++', ponieważ GHC eliminuje wytworzoną listę pośrednią. –

listy Haskell są oddzielnie połączone, więc cons, head i tail O (1), podczas gdy init i last O (n).

Jeśli potrzebujesz lepszej wydajności, rozważ użycie typu Seq z Data.Sequence, który zapewnia O (1) dostęp do obu końców listy. Wewnętrznie używa 2-3 finger trees.

Źródło

2013-02-25 08:50:22

Wewnętrzna reprezentacja list Haskella?

Odpowiedz

Powiązane problemy