21

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

真实世界的 Haskell

在像这样的简单基准测试中，即使是用 Python 等解释性语言编写的程序也能胜过使用 String 的 Haskell 代码一个数量级。

Haskell 中的高效字符串实现

由于String只是[Char]，即Char的链表，这意味着String的引用局部性较差，再次意味着String在内存中相当大，至少为N *（21bits + Mbits），其中N是字符串的长度，M 是指针的大小 (...)。编译器不太可能将字符串优化为循环等。

我知道 HaskellByteString的 s（和Arrays）有几种不错的风格，它们可以很好地完成这项工作，但我希望默认实现是最有效的实现。

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

4

3 回答 3

22

为什么 Haskell 的默认 String 实现是单链表

因为单链表支持：

  • 通过模式匹配进行归纳
  • 具有有用的属性，例如 Monad、Functor
  • 是适当参数多态的
  • 天生懒惰

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

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

于 2012-12-13T18:20:41.873 回答
12

Efficiency is only one axis to measure an abstraction on. While lists are pretty inefficient for text-y operations, they are darn convenient in that there's a lot of list operations implemented polymorphically that have useful interpretations when specialized to [Char], so you get a lot of reuse both in the library implementation and in the user's brain.

It's not clear that, were the language being designed today from scratch with our current level of experience, the same decision would be made; however, it's not always possible to make decisions perfectly before experience is available.

于 2012-12-13T17:56:17.617 回答
4

在这一点上，它可能是历史性的：使事情ByteString如此高效的优化是最近的，而[Char]比它们早了很多年。

于 2012-12-13T17:56:48.337 回答