storing highly shared data structures

[Einar Karttunen]

On 22.12 14:43, Christian Maeder wrote:
> How can I detect this sharing in order to avoid traversing the very
> same symbol table for every symbol?

By using System.Mem.StableName
SerTH (http://cs.helsinki.fi/u/ekarttun/SerTH/) implements this,
so you can look at the source for pointers.

> I've tried to use a "Map (Ptr ()) ShATerm". So before traversing an
> object I look up its address and check if is was traversed before (if
> not I traverse it and store it in my map for future lookups).

GHC can move the objects in memory.

> 2.) A single "Map (Ptr ()) ShATerm" does not work! It seems that
> sometimes objects are shared that have different types (as tests
> revealed). This seems obvious for newtypes but also happens (I think)
> without newtype declarations.

Yes, this is quite evil. For example the empty list can be shared
across type boundaries. Also phantom types can share the same
address. In addition you have to worry about libraries using
unsafeCoerce#

> So, I'm now thinking if I should try using the type of my data as key
> as well, i.e. using "Map (TypeRep, Ptr ()) ShATerm" to avoid duplicate
> traversals.

TypeRep is not Ord iirc, which makes this harder. Of course you can
show it and then use that.

- Einar