[erlang-questions] Strings as Lists

Alexey Shchepin <>
Thu Feb 14 20:37:28 CET 2008


Hello, Richard!

On Tue, 12 Feb 2008 18:00:30 +0100, you said:

 RC> Strings as lists is simple and flexible (i.e., if you already have lists,
 RC> you don't need to add another data type). Functions that work on lists,
 RC> such as append, reverse, etc., can be used directly on strings; you don't
 RC> need to program in different styles if you're traversing a list or a
 RC> string; etc. Other languages that represent strings as lists include
 RC> Prolog (which was a big influence on Erlang) and Haskell. That said, in
 RC> larger systems it is better to represent string constants in a more
 RC> space-efficient way. Binaries let you do this in Erlang, but they were a
 RC> later addition to the language, and the syntax for constructing and
 RC> decomposing binaries came even later.

Some time ago I made a VList[1] implementation and altered it to handle
efficiently lists of bytes.  If list construction and destruction operations
(cons, hd, tl) are replaced transparently by compiler to VList ones, then you
get:

Pros:
  * No need to rewrite programs and add new syntax, just continue to use
    lists.
  * Lists of bytes consume approximately from n to 2n bytes.
  * Lists containing other values consume approximately from n to 2n words.
  * length/1, lists:nth/2, and lists:nthtail/2 work in O(log n) time.
  * Binaries can use the same representation (this way it is efficient to
    add bytes to the beginning while in the current implementation it is
    efficient to add them to the end of a binary).

Cons:
  * List destruction allocates memory (but can sometimes be optimized by
    compiler).
  * Cons, hd and tl are slower than traditional list implementation, though a
    program can work faster due to less memory usage and less GC load.
  * Small lists consume more memory.

[1] http://en.wikipedia.org/wiki/VList
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 2061 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080214/18334789/attachment.bin>


More information about the erlang-questions mailing list