Why are strings linked lists?

[Robert Will]

hi,

In relation to my other message, I can contribute to this question.  I
think it is very important and useful to consider Strings as Sequences of
Characters.  And independently of the issue discussed elsewhere -- whether
Characters should be a type or a class -- I am asking whether Sequences
should be "linked list", that is functional stacks in Haskell.  (Stacks
because cons, head, tail are primitive.)

> 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!

Of course, Packed Arrays will not really change this, but any
implementation of Sequences, where ++ doesn't copy its first argument
will.

In Dessy's standard implementation the above will only use a few bytes...
http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/

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

Again, while PackedArrays can't do all of that better, there are a purely
functional data structures, that can.  I estimate that 99% of all uses of
Sequence will work fine with the standard implementation or with Deques,
found on the same page above.

> 3. They make learning Haskell harder.

Why is 'last' so much slower than 'head'?  Why is 'head' not called
'first'?  Why does 'but_last' (aka init) copy the list, but 'but_first'
(aka tail) does not?

The question is whether we want to teach abstraction or stack
programming...


Robert