Dlaczego domyślna implementacja łańcucha Haskella jest połączoną listą znaków?

Fakt, że domyślna implementacja Haskella String nie jest wydajna, zarówno pod względem szybkości, jak i pamięci, jest dobrze znana. O ile mi wiadomo, na ogół w Haskell są stosowane jako listy pojedynczo powiązane, a dla większości małych/prostych typów danych (np. Int) nie wydaje się to dobrym pomysłem, ale dla String wydaje się, że to całkowita przesada. Niektóre z opinii na ten temat to:Dlaczego domyślna implementacja łańcucha Haskella jest połączoną listą znaków?

Real World Haskell

na prostych wskaźników, takich jak to, a nawet programów napisanych w językach interpretowanych, takich jak Python może przewyższyć kod Haskell, który używa String o rząd wielkości.

Efficient String Implementation in Haskell

Ponieważ ciąg jest po prostu [Char], który jest powiązany lista Char, to znaczy Struny mają słabą lokalizację odniesienia i znów oznacza, że Struny są dość duże w pamięci, co najmniej jest to N * (21 bitów + megabitów), gdzie N jest długością łańcucha, a M jest wielkością wskaźnika (...). Struny są znacznie mniej podatne na zoptymalizowanie do pętli itp. Przez kompilator.

wiem, że Haskell ma ByteString s (i Array e) w kilku przyjemnych smakach i że mogą wykonać zadanie ładnie, ale spodziewałbym domyślna implementacja jest najbardziej wydajny jeden.

TL; DR: Dlaczego domyślna implementacja Haskella String jest listą pojedynczo połączoną, mimo że jest bardzo nieefektywna i rzadko używana w aplikacjach świata rzeczywistego (z wyjątkiem tych naprawdę prostych)? Czy są jakieś historyczne powody? Czy łatwiej jest wdrożyć?

Źródło

2012-12-13 ljedrz

Zakładam, że to dlatego, że '[Char]' jest okropnie wygodne. –

Czuję, że warto wspomnieć, że 'ByteString' zdecydowanie nie jest tekstem, a' Array' nie jest dużo lepszym - 'Text' jest naprawdę dobrym rozwiązaniem. –

Haskell/= GHC. Posiadanie reprezentacji ciągów "żółtych przez cały czas" było godnym pochwały projektem na początku czasów Haskella, kiedy było kilka różnych kompilatorów/interpretatorów. –

Dlaczego domyślna implementacja String Haskell jest pojedynczo-linked lista

Bo pojedynczo-połączone wykazy wspierać:

indukcję poprzez wzór pasujący
mają cenne właściwości, takie jak Monady , Funktor
są prawidłowo parametrycznie polimorficzne
są z natury leniwi

i tak String jak [Char] (punkty Unicode) oznacza typ ciąg, który pasuje do celów językowych (od 1990), a przede wszystkim są „za darmo” z biblioteki na liście.

Podsumowując, historycznie projektanci języków bardziej interesowali się dobrze zaprojektowanymi podstawowymi typami danych niż współczesnymi problemami przetwarzania tekstu, więc mamy elegancki, łatwy do zrozumienia, łatwy do nauczenia typ, który nie jest dość porcja tekstowa w Unicode i nie jest gęstym, spakowanym, ścisłym typem danych.

Źródło

2012-12-13 18:20:41

Wszystkie odpowiedzi dostarczyły mi nowych cennych informacji, ale twoja jest najbardziej kompletna (co wydaje się być cechą wspólną dla wszystkich twoich odpowiedzi :)). – ljedrz

To są bardzo ładne właściwości. Są to niektóre z kluczowych powodów, dla których dana osoba używałaby Haskella w innych językach. To zadziwiające, że istnieją alternatywne implementacje ciągów, które je podnoszą. Dlaczego kompilator nie może wydajnie wdrożyć [Char]? Nieco uogólnione rozwiązanie tego problemu może sprawić, że wszystkie rzeczy staną się bardziej wydajne. –

@PaulHarrison: Po pierwsze, inni są mniej leniwi, a kompilator nie uczyni zaostrzonymi, dopóki nie będzie pewności, że to nie zmieni zachowania programu. Na ogół nie jest to łatwe zadanie. –

Wydajność to tylko jedna oś do pomiaru abstrakcji. Chociaż listy są dość nieefektywne dla operacji text-y, są one wygodne w tym, że wiele operacji na listach jest zaimplementowanych polimorficznie, które mają przydatne interpretacje, gdy są wyspecjalizowane w [Char], dzięki czemu uzyskujesz wiele ponownego wykorzystania zarówno w implementacji biblioteki, jak i w użytkowniku. mózg.

Nie jest jasne, czy gdyby dzisiejszy język był projektowany od zera z naszym obecnym doświadczeniem, ta sama decyzja byłaby podjęta; jednak nie zawsze jest możliwe podejmowanie decyzji doskonale, zanim będzie dostępne doświadczenie.

Źródło

2012-12-13 17:56:17

Dość kilka operacji tekst-y to, pojęciowo, operacje na sekwencjach znaków unicode które raz przekraczają ciąg znaków. "Sprawny" tekst nie występuje, jeśli wymusza na nim dużą ilość danych naraz, zamiast wymuszać tylko kilka "(:)" naraz. Problemy z używaniem "[Char]" nie są tak katastrofalne, jak się czasem opisuje. –

W tym momencie, to prawdopodobnie historyczny: optymalizacje, które dokonały rzeczy jak ByteString tak wydajne są niedawnej, natomiast [Char] poprzedza je wszystkie przez wiele lat.

Źródło

2012-12-13 17:56:48

Dlaczego domyślna implementacja łańcucha Haskella jest połączoną listą znaków?

Odpowiedz

Powiązane problemy