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