Pros and cons of representing strings as lists of characters

Question

I am writing a compiler for my programming language (both almost complete), but they are stuck in the, I would call, "String vs List-of-Char dilemma". Maybe some more experienced compiler programmer could help.

It is a functional, strongly typed (with inference) and almost pure (immutable vars) language. As I could perceive, using a list of chars is better for simplicity/generality of the language. But it adds complexity to the runtime/stdlib, because the user may require sometimes to print a List-of-Char as a text and sometimes as a list.

Perhaps a built-in function just to print a List-of-Char as text would be a good compromise? I may be missing something here.

In the other hand, defining a "String" type different from "List", requires duplicity of all list functions like "head", "tail", "replace" etc. to preserve the soundness and simplicity of the type system. It also requires duplicity from the user when implementing similar methods.

Perhaps a built-in function just to convert a List-of-Char to String and vice-versa would be a good compromise? I may also be missing something here.

obs.: The code is in github if anyone has interest into delving in the problem.

Answer 1

I'd say that the main reason for having a separate String representation is performance. For example, Haskell defines a string to be a list of characters type String = [Char]. But in many applications it turns out that this is too slow - you have one constructor for every character, which requires a lot of work from the garbage collector. Then of course you have to duplicate most of the string functions, but the benefit is that you can implement them natively to be very fast.

So I'd suggest: If you are concerned about performance, define a native string type. If not, use list of characters instead.