Warum ist Haskells Standard-String-Implementierung eine verkettete Liste von Zeichen?

Question

Die Tatsache, dass Haskells Standard String Implementierung sowohl hinsichtlich der Geschwindigkeit als auch des Arbeitsspeichers nicht effizient ist, ist bekannt. Soweit ich weiß, sind die [] lists im Allgemeinen in Haskell als einfach verknüpfte Listen implementiert und für die meisten kleinen/einfachen Datentypen (z. B. Int) scheint es keine sehr gute Idee zu sein, aber für String scheint es wie totaler Overkill. Einige der Meinungen zu diesem Thema sind:

Real World Haskell

Auf einfache Benchmarks wie dies auch in interpretierten Sprachen geschriebene Programme wie Python kann Haskell Code entwickeln, den String von einer Größenordnung verwendet.

Efficient String Implementation in Haskell

Da ein String ist nur [Char], dass eine Liste von Char verknüpft ist, bedeutet dies Strings schlechte Referenzlokalität haben, und bedeutet wiederum, dass Strings im Speicher ziemlich groß ist, zumindest ist es N * (21 Bits + Mbits), wobei N die Länge der Zeichenkette und M die Größe eines Zeigers (...) ist. Es ist viel weniger wahrscheinlich, dass Strings durch den Compiler für Schleifen usw. optimiert werden können.

Ich weiß, dass Haskell ByteString s hat (und Array s) in mehr schönen Aromen und dass sie schön die Arbeit machen können, aber ich würde die Standardimplementierung erwartet, dass der effizienteste sein.

TL: DR: Warum ist Haskells Standard String Implementierung eine einfach verknüpfte Liste, obwohl es schrecklich ineffizient und selten für reale Anwendungen (mit Ausnahme der wirklich einfachen) verwendet wird? Gibt es historische Gründe? Ist es einfacher zu implementieren?

Answer 1

Warum ist Standard String-Implementierung Haskell eine einfach verkettete Liste

Weil einfach verkettete Listen unterstützen:

• Induktion über Muster
• haben nützliche Eigenschaften, wie Monad passend , Functor
• sind richtig parametrisch polymorph
• sind natürlich faul

und so String als [Char] (Unicode Punkte) bedeutet einen String-Typ, der die Sprache Ziele (Stand: 1990) passt und im wesentlichen kommen „kostenlos“ mit der Liste Bibliothek.

Zusammenfassend, in der Vergangenheit waren die Sprachdesigner mehr in gut gestalteten Kerndatentypen interessiert, als die modernen Probleme der Textverarbeitung, so dass wir eine elegante, leicht zu verstehen, leicht zu lehren String Art, das ist nicht ein ziemlich unicode text chunk, und ist kein dichter, gepackter, strenger Datentyp.

Answer 2

Effizienz ist nur eine Achse, um eine Abstraktion zu messen. Während Listen für Text-y-Operationen ziemlich ineffizient sind, sind sie insofern praktisch, als es eine Vielzahl von polymorph implementierten Listenoperationen gibt, die nützliche Interpretationen haben, wenn sie auf [Char] spezialisiert sind, so dass Sie viel Wiederverwendung sowohl in der Bibliotheksimplementierung als auch im Benutzer erhalten Gehirn.

Es ist nicht klar, dass, wenn die Sprache heute von Grund auf mit unserer derzeitigen Erfahrung entwickelt würde, die gleiche Entscheidung getroffen würde; Es ist jedoch nicht immer möglich, Entscheidungen perfekt zu treffen, bevor Erfahrungen verfügbar sind.

Answer 3

An dieser Stelle ist es wahrscheinlich historisch: Die Optimierungen, die Dinge wie ByteString so effizient sind letzten gemacht haben, während [Char] sie alle mit vielen Jahren zurückdatiert.