Why are strings linked lists?

[Wolfgang Jeltsch]

Am Freitag, 28. November 2003 04:32 schrieb Ben Escoto:
>Hi, can someone tell me why Haskell strings are linked lists?

I think they are lists because there is already good support for lists in 
Haskell. You can just take the many list functions and apply them directly to 
strings.

You could then ask why lists are defined via an algebraic data type and not 
via an array type. I think, this is because algebraic data types are 
fundamental in Haskell and arrays are just there because of efficiency. In 
addition, with an algebraic data type you are able to use such nice things 
like pattern matching.

> [...]

> 1.  Today I spend a few hours trying to track down a memory leak.  It
>     turns out I just didn't realize how much space a string takes up.
>     On my machine "replicate 5000000 'a'" will use 90MB of space!

You have to take into account that Chars (in GHC) take 4 bytes of memory 
because they denote Unicode codepoints. 5,000,000 times 4 bytes is already 20 
MB. (The rest is only a constant factor. ;-))

> 2.  They are extremely slow for most operations like writing to disk,
>     adding something to the end, concatenation, etc.

Well, there are solutions for avoiding the quadratic time problem with 
concatenation like the ShowS thing in the prelude or my "EC list" 
implementation found under
    http://cvs.sourceforge.net/viewcvs.py/seaweed/code/Seaweed/Core/Lists.hs
(Well, I don't know how big the overhead for building the internal data 
structures of EC lists is.)

> 3.  They make learning Haskell harder.  Lazy IO functions like
>     hGetContents are kind of slick in a shallow way, but I was
>     confused about the Haskell IO model because I thought of this as
>     the normal way IO was done, not something you could only set up
>     through unsafeInterleaveIO or similar.

These are problems concerning lazy I/O and not the fact that strings are 
implemented as linked lists.

> [...]

Wolfgang