Kilka miesięcy temu przeczytałem gdzieś skuteczne podejście do dodawania list i dodawania ich do innych list w O (1), reprezentując je za pomocą składów funkcji, które po ocenieniu budują w O (n) wynikową listę.Efektywna lista dołączeń/przedkładania przez skład funkcji
Niestety nie pamiętam źródła tego artykułu lub (jeśli istnieje) nazwy tej techniki/podejścia. Czy masz referencje na ten temat?
Struktura danych nazywana jest listą różnic (lub skrótem DList). Możesz znaleźć domyślną implementację tego in a library available on Hackage.
Jak wspomniano, pełny opis można uzyskać od a chapter in Real World Haskell on the subject.
Świetnie, dzięki! Właśnie tego szukałem. Wyszukując trochę dla "DList", dowiedziałem się, że faktycznie szukałem rozdziału 13 "Real World Haskell" Dona Stewarta ... tutaj jest pełne wyjaśnienie, jak działają te listy: http: // book. realworldhaskell.org/read/data-structures.html#data.dlist Czy możesz umieścić link do książki w odpowiedzi jako przyszłe odniesienie, proszę? Dzięki –
Jest to również wspomniane w LJAAH: http://learnyouahaskell.com/for-a-few-monads-more, rozdział "Listy różnic" – efie
@Riccardo oryginalna lista różnic urodził się oczywiście w Prologu i składa się z niczego więcej niż pojedynczo połączonej listy, która przenosi także wskaźnik do ostatniej komórki, dzięki czemu można ją skutecznie rozszerzyć. W nieobracającym się prologu, jak w Haskell, po ustawieniu wskaźnika nie można go zmienić. Jest on łatwo implementowany w języku C i można go uczynić niezmiennym przez dodanie innego pola danych, * długości *, do struktury danych, więc żaden dostęp za tym punktem nie jest dozwolony. Po jej rozszerzeniu można utworzyć kopię o nowej długości, ale o tej samej liście podstawowej. (realizatorzy, Uwaga!) :) –
Musisz myśleć o ShowS i przyjaciołach z Preludium. Zobacz here.
(Prawdopodobne) pierwsze pojawienie się było w pracy Johna Hughesa "A Novel Representation of Lists i jej zastosowanie do funkcji" Reverse "(uważam, że wcześniej były to folklory) - stąd są one również nazywane" Hughes Lists ". Zauważ, że wspierają tylko efektywną ** konstrukcję ** - pakiet DList w Hackage ma API wspierające _trospekcję_, ale aby zaimplementować introspekcję, musisz dokonać metamorfozy w zwykłą listę i wycofać się ponownie. Jest to nieefektywne - jeśli chcesz introspekcji potrzebujesz innej struktury. –
Jest to wystarczający kompromis, gdy introspekcja nie jest potrzebna. Dziękuję za wskazanie tego. Nie szukam teraz struktury danych, ale chciałbym po prostu zapoznać się z implementacją dla list różnicowych/Hughes. –