lje*_*drz 21 string performance haskell linked-list
Haskell的默认String实现在速度和内存方面都不高效这一事实是众所周知的.据我所知[] lists,通常在Haskell中实现单链接列表和大多数小/简单数据类型(例如Int)它似乎不是一个非常好的主意,但因为String它似乎完全矫枉过正.关于此事的一些意见包括:
在像这样的简单基准测试中,即使用Python等解释语言编写的程序也可以胜过使用String一个数量级的Haskell代码.
由于String只是[Char],这是Char的链接列表,这意味着字符串的引用局部性较差,并且再次意味着字符串在内存中相当大,至少它是N*(21bits + Mbits)其中N是字符串的长度,M是指针的大小(...).字符串不太可能被编译器优化为循环等.
我知道Haskell的ByteStrings(和Arrays)有几种不同的风格,并且它们可以很好地完成工作,但我希望默认实现是最有效的.
TL; DR:为什么Haskell的默认String实现是单链表,即使它非常低效并且很少用于真实世界的应用程序(除了非常简单的应用程序)？有历史原因吗？实施起来更容易吗？
Don*_*art 20
为什么Haskell的默认String实现是单链表
因为单链接列表支持:
因此String为[Char](UNICODE点)是指符合语言学习目标(如1990年)的字符串类型,而且基本上都可以"免费"使用的名单库.
总之,历史上语言设计者对设计良好的核心数据类型感兴趣,而不是文本处理的现代问题,所以我们有一个优雅,易于理解,易于教授的String类型,这不是一个unicode文本块,并不是一个密集,包装,严格的数据类型.
Dan*_*ner 12
效率只是衡量抽象的一个轴.虽然列表对于text-y操作效率非常低,但是它们非常方便,因为有许多列表操作以多态方式实现,在专门用于解释时[Char]有很多有用的解释,因此在库实现和用户的大脑中都可以获得大量的重用.
目前尚不清楚,如果我们目前的经验水平是从头开始设计的,那么同样的决定也是如此; 然而,在经验可用之前,并不总是能够做出完美的决策.