[Haskell-cafe] Structural sharing in haskell data structures?

[Tillmann Rendel]

Hi,

Andrew Wagner wrote:
> So I'm just curious, does GHC use
> structural sharing or something similar? 

Structural sharing is not a feature of implementations, but of 
libraries. Consider this example:

   -- a function to "change" the head of a list
   replaceHead y xs = y : tail xs

   -- a big list
   xs = [1..10000]

   -- two new list with changed head
   ys = replaceHead 42 xs
   zs = replaceHead 27 xs

   -- the length of our lists
   n = length xs + length ys + length zs

In this example, n will be 30000, but even after evaluation xs, ys and 
zs, we have only 10002 cons cells allocated, because 9999 cons cells are 
shared between xs, ys and zs. This happens automatically in every 
language with references or pointers. However, it is only sane to do 
with immutable data structures, so programmers have to add extra code to 
explicitly avoid structural sharing in impure languages.

Another example:

   xs = 1 : xs

This list is infinite, but we have only one cons cell allocated.

   Tillmann