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