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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
