Databases
StackOverflow2013
Postsdbo
POWhy is Haskell's default string implementation a linked list of chars?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy is Haskell's default string implementation a linked list of chars?
    text
    copied!<p>The fact that Haskell's default <code>String</code> implementation is not efficient both in terms of speed and memory is well known. As far as I know the <code>[] lists</code> in general are implemented in Haskell as singly-linked lists and for most small/simple data types (e.g. <code>Int</code>) it doesn't seem like a very good idea, but for <code>String</code> it seems like total overkill. Some of the opinions on this matter include:</p> <p><a href="http://book.realworldhaskell.org/read/efficient-file-processing-regular-expressions-and-file-name-matching.html" rel="nofollow noreferrer">Real World Haskell</a></p> <blockquote> <p>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.</p> </blockquote> <p><a href="https://stackoverflow.com/questions/576213/efficient-string-implementation-in-haskell">Efficient String Implementation in Haskell</a></p> <blockquote> <p>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.</p> </blockquote> <p>I know that Haskell has <code>ByteString</code>s (and <code>Array</code>s) in several nice flavors and that they can do the job nicely, but I would expect the default implementation to be the most efficient one. </p> <p>TL;DR: Why is Haskell's default <code>String</code> implementation a singly-linked list even though it is terribly inefficient and rarely used for real world applications (except for the really simple ones)? Are there historical reasons? Is it easier to implement?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload