string - 为什么 Haskell 的默认字符串实现是一个字符的链表？

Question

事实上，Haskell 的默认 String众所周知，实现在速度和内存方面效率不高。据我所知[] lists通常在 Haskell 中作为单链表实现，对于大多数小/简单的数据类型(例如 Int )，这似乎不是一个好主意，但对于 String这似乎完全是矫枉过正。关于这个问题的一些意见包括:

Real World Haskell

On simple benchmarks like this, even programs written in interpreted languages such as Python can outperform Haskell code that uses String by an order of magnitude.

Efficient String Implementation in Haskell

Since a String is just [Char], that is a linked list of Char, it means Strings have poor locality of reference, and again means that Strings are fairly large in memory, at a minimum it's N * (21bits + Mbits) where N is the length of the string and M is the size of a pointer (...). Strings are much less likely to be able to be optimized to loops, etc. by the compiler.

我知道 Haskell 有 ByteString s(和 Array s)有几种不错的风格，并且它们可以很好地完成工作，但我希望默认实现是最有效的实现。

TL;DR: 为什么 Haskell 的默认值是 String实现一个单链表，即使它非常低效并且很少用于现实世界的应用程序(除了非常简单的应用程序)？有历史原因吗？更容易实现吗？

Answer 1

Why is Haskell's default String implementation a singly-linked list

因为单链表支持:

通过模式匹配进行归纳

具有有用的属性，例如 Monad、Functor

是适当的参数多态

天生懒惰

等等 String如 [Char] (unicode 点)表示符合语言目标的字符串类型(截至 1990 年)，并且基本上随列表库“免费”提供。

总之，从历史上看，语言设计者对设计良好的核心数据类型更感兴趣，而不是文本处理的现代问题，所以我们有一个优雅、易于理解、易于教授的 String类型，它不是一个 unicode 文本 block ，也不是一个密集的、打包的、严格的数据类型。