summary of storing highly shared data structures

[Christian Maeder]

I wrote:
> However, shared ATerms are always different for different types,
> because the corresponding data constructors are different.

This isn't quite true. The shared ATerm for the empty list is the same 
for all instances.

> Finally, _reading in_ shared ATerms is fast, since ghc seems to exploit 
> the sharing given by the injective ATermTable.

This was also wrong. The ATermTable as "IntMap ShATerm" was not enough, 
because all objects were constructed anew from the same or different 
ShATerms. I had to setup an additional "IntMap Dynamic" for creating 
shared data structures. It was no fun to make everything "Typeable" (and 
having no Ord instance for TypeRep).

Simon suggested to use StableName or StablePtr. I did not use StablePtr, 
because it lacks a hashing function!

I wasn't happy with StableName either, because
  1) it required IO
  2) System.Mem.StableName is marked "non-portable"
     (without a reason in the haddock documentation)
  3) There was no coercion function "StableName a -> StableName b"

I coerced all my objects with makeStableName and GHC.Prim.unsafeCoerce# 
to "StableName ()" (I became non-portable, anywy.)

Now I could use "Data.HashTable (StableName ()) Value" since I was in 
the IO monad anyway. (The Value is basically an Int, but here I want to 
avoid the potential confusion with the key.)

For the sake of interest I also tried "IntMap [(StableName (), Value)]" 
using hashStableName as IntMap key. (An IntMap is also used in 
http://cs.helsinki.fi/u/ekarttun/SerTH that Einar Karttunen pointed to)

It turned out that the IntMap was not slower than the HashTable (What is 
HashTable good for, then? Why is it so slow?)

Since I used hashStableName to get a key for my IntMap, I see no reason 
why StableName should not have an Ord instance, in order to avoid the 
whole hashing with lists (although a "Data.Map (StableName ()) Value" 
may not be faster).

Summerizing, the user-friendliness (at least) of System.Mem.StableName 
should be improved (also with respect to the "+RTS -A10m" business for 
performing makeStableName).

Cheers Christian