Haskell’s String type is an alias for [Char] (i.e. a linked list of Chars). Does any other language use an implementation of strings like this?

  • 4
    Did you know that Haskell also has a Text type which is a conventional way of implementing strings - i.e. just like java.lang.String? – ErikR Jun 19 '16 at 22:10
  • As a side note, Scala lets you implicitly treat a string as a list of chars, even though the underlying representation is a regular java string. – Karl Bielefeldt Jun 20 '16 at 18:28
  • Haskell was designed as a replacement for a language called Miranda. Pretty-much any dubious design decision in Haskell (including Strings-as-linked-lists) can be traced back to being the way it was done in Miranda... – Jules Jun 20 '16 at 21:12

Yes. Erlang does the same, as well as quite a few other functional programming languages.

Using strings as a list of chars makes them very easy to pattern match and reason about. However, their performance is relatively bad:

  • accessing the nth character in a string takes walking through all n-1 items before it. This is thus linear in time.
  • appending strings is slow for the same reason (you need to loop through all characters of the first string)
  • in a linked list, you need to store both a character and a pointer to the next character. This takes a lot more memory (for each character, you need both the character itself plus a pointer to the next memory location, which on most systems actually takes more space than the character itself).

Also, Unicode, where one grapheme might consist of multiple characters, has made them even less practical, as this makes the pattern matching on characters very awkward again.

Often, these languages also have other ways to deal with strings that are faster, but harder to manipulate. For instance, Haskell has the Text type, and Erlang has Binaries that can be treated as strings.

  • 2
    "twice as much memory" is rather optimistic. For the common case of ASCII characters (which would take 1 byte as part of a UTF-8 string) you'd need 8+1 bytes for a node on a 64 bit system. And that isn't even taking allocator overhead or alignment, so a node will likely end up with 16 bytes of memory. For Japanese text where each character takes 3 bytes of UTF-8 the difference is still a factor of 5 for long strings. – CodesInChaos Jun 20 '16 at 9:09
  • 1
    "accessing the nth character in a string takes walking through all n-1 items before it. This is thus linear in time. " -- this is also true of strings stored as an array of UTF8 bytes or UTF16 words, as these are variable length encodings so you need to interpret all other bytes/words until you get to the one that starts the character you're looking for. This hasn't stopped this representation being the most common. – Jules Jun 20 '16 at 21:09
  • @CodesInChaos You are very right. I have changed the faulty 'rougly twice as much memory' part to a slightly more general statement. Jules: This is indeed true. Of course, replacing part of a string is another case where linked lists have a problem over arrays (assuming that the new string does not result in new memory needing to be allocated for the array, which would complicate it somewhat), because if I replace something in a linked list, I need to replace everything in front of it as well, as the pointers no longer work. – Qqwy Jun 20 '16 at 22:59
  • Re, "the common case of ASCII characters", Slowly, but surely, it's becoming less common. Won't be long I expect before we start seeing programming languages (or programming language variants) with non-ASCII keywords. – Solomon Slow Jun 20 '16 at 23:10

The "abc" syntax in Prolog is usually a shorthand notation for a list of character codes, i.e. [97,98,99], which is also the case in Erlang. See this question for details. When a Prolog implementation supports a custom string type (e.g. ECLiPSe/SWI/YAP), there are predicates to convert from and to lists of character codes.

  • Think the OP was more interested in "complex" string types, i.e. a minimal string is always a series or list of character codes. But while I don't know Haskell (just some basics), this sounds like String would store more metadata per node/character, i.e. the linked list connection to the next node. – Mario Jun 20 '16 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.