Why are strings linked lists?

[Matthias Kilian]

On Fri, Nov 28, 2003 at 11:31:51AM +0100, Wolfgang Jeltsch wrote:
> >     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. ;-))

No, in the above example there's only one single 'a' but 5000000
(:) and one [] heap-allocated cells.

For example,

    let f = replicate 5000000 in f (f 'a')

will use only about twice (and not 5000000 times) the memory of the
initial example. Exactly: 10000000 * size of (:) + size of 'a' + size of [].

So the only relevant thing is the list constructor (:) which needs two
pointers to its arguments, and typically another pointer for housekeeping
(depending on the runtime implementation). That typically makes 12 bytes
per constructor (on a 32 bit architecture).

Regards,
	Kili

-- 
Denken ist schwer, darum urteilen die meisten.
[Carl Gustav Jung]