Simon Peyton-Jones wrote:
For various applications (including identifying common sub-expressions, and version tracking in GHC), I'd like a Haskell library that supports simple fingerprint operations.
Note that for CSE and hash-consing, there is a no-collision yet very efficient way of fingerprinting (with a drawback, of course :). The starting point is the question "why does cryptographic hashing work"? I mean, uniquely serializing (gödel numbering) a tree like newtype Exp = Exp (ExpF Exp) data ExpF a = Zero | One | Add a a | Mult a a deriving (Functor, Foldable, Traversable) takes an amount of bits proportional to its size (number of constructors). So, how can we expect a simple 128-bit number to have only few collisions for a collection of medium-sized trees? The answer is that the collection is much too small, no computer will ever be able to count (or construct said trees) from 1 to 2^128 in eons. 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 type StateC a = Collection -> (Collection, a) deriving (Monad) cse :: Exp -> StateC GödelNumber cse = cata hashCons hashCons :: ExpF (StateC GödelNumber) -> StateC GödelNumber hashCons x0 = \c0 -> let (c,x) = sequence x0 c0 in case lookup x c of Maybe g -> (c,g) Nothing -> let g = size c + 1; c' = insert x g c in (c',g) where sequence :: ExpF (StateC GödelNumber) -> StateC (ExpF GödelNumber) sequence = Data.Traversable.sequence 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? Regards, apfelmus