On Oct 11, 2007, at 4:33 PM, apfelmus wrote:
...
So, the idea is to use a "local gödel numbering" and uniquely
number the and only the trees that are actually constructed (no
collisions, but few in numbers). In other words, every new tree
created gets the gödel number size collection + 1 and we can
simply use
type GödelNumber = Word32
assuming that no more than 4G of trees will ever be constructed.
For fast hash-consing, the collection itself is a (generalized) trie
type Collection = ExpF GödelNumber ~~> Maybe GödelNumber
mapping each new top of a tree (constructor + gödel numbers for
already known subtrees) to either Just its gödel number or Nothing
when it's not in the collection yet.
With this, CSE becomes a catamorphism that allocates new gödel
numbers if necessary
...
CSE in the sense that all common subexpressions now have the same
gödel number.
Of course, the drawback compared to "free-form" fingerprinting is
that the fingerprinting and the collection now depend on each
other. But for CSE, we have to carry the collection around anyway.
I don't know any references for that method since I came up with it
myself and haven't searched around yet. Any pointers?
Actually, the paper that Lauri cited in his message mentions
essentially this technique; this is equivalent to the permutation T()
that they impose when fingerprinting a DAG. That citation again:
http://citeseer.ist.psu.edu/broder93some.html
But it's generally pretty well known.
-Jan
_______________________________________________
Haskell mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell
