The Haskell String Situation

http://www.stephendiehl.com/posts/strings.html

by paulddraper • 7 years ago

4 1 7 years ago

triska• 7 years ago

Regarding the following quote about type String = [Char]:

“This is not only a bad representation, it’s quite possibly the least efficient (non-contrived) representation of text data possible and has horrible performance in both time and space.”

It is true: This is slow if String is internally implemented so naively that it is "really" a list of characters. However, better internal representations are possible, i.e., internal handling of strings as if they were lists of characters, so that a String appears to Haskell code as a perfectly "normal" list, while internally being represented much more efficiently as a sequence of raw bytes.

In other words, the fact that String has this specific type (i.e., [Char]) does not mean that it needs to be implemented in the most naive way possible by the Haskell compiler or interpreter.

Prolog is in a very similar situation:

For convenience to Prolog programmers, strings in double quotes (such as "abc") ought to be interpreted as lists of characters (such as [a,b,c]). So, to Prolog code, strings should appear as if they were "normal" lists. This makes them amenable to Prolog's built-in parsing mechanisms and many predicates over lists that are already available.

At the same time, strings should be internally represented more efficiently, as sequences of bytes in memory.

Recently, Mark Thom has expressed his interest in implementing such a solution in Scryer Prolog:

https://github.com/mthom/scryer-prolog/issues/95

The same idea may be applicable to Haskell, to combine convenience with efficiency when handling strings.

The Haskell String Situation

Related Stories