[Haskell-cafe] Structural sharing in haskell data structures?
rendel at cs.au.dk
Tue May 12 19:25:55 EDT 2009
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.
xs = 1 : xs
This list is infinite, but we have only one cons cell allocated.
More information about the Haskell-Cafe