Sat Dec 31 09:46:36 EST 2011
Mapping trees to integers
More specifically in Haskell: given a tree which is only terminated in
nodes that are temselves mappable to integers, how to map such a tree
to an integer (i.e. for exact hashing?)
Mapping (positive) integer sequences to integers is quite
straightforward. As a base use the primes, and express the tuples as
prime powers. Anything that can be mapped to positive integer
sequences can be encoded that way.
So how about trees?
Since part of the problem is solved, the question remains: how to map
an arbitrary tree into a sequence of positive integers?
Let's start with this 
Actually.. It's a lot simpler maybe to just map everything to bits.
Here's the two implementations mapping the datatype Type to integers.
data TypeName = AFloat | AInt | ABool | AVoid -- atomic
| ATree TypeTree -- composite
| AType Int -- indexed type (see PrettyC.hs)
data TypeTree = AAtom Type
| ACons Type Type
data Type = Type TypeName TypeOrder
type TypeOrder = Int
Prime-encoded positive sequences:
primes :: [Integer]
primes = sieve [2..]
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
hashPos :: [Integer] -> Integer
hashPos is = hp is primes where
hp  _ = 1
hp (i:is) (p:ps) = p ^ i * hp is ps
typePos :: Type -> [Integer]
typePos = typ where
name AFloat = 
name AInt = 
name ABool = 
name AVoid = 
name (AType i) = [5, 1+i]
name (ATree t) =  ++ tree t
tree ANil = 
tree (AAtom t) =  ++ typ t
tree (ACons t1 t2) =  ++ typ t1 ++ typ t2
typ (Type n o) = name n ++ [1+o]
hashBin :: [Integer] -> Integer
hashBin = hb where
hb  = 1
hb (b:bs) = b + 2 * (hb bs)
typeBin :: Type -> [Integer]
typeBin = typ where
-- One case, no prefix.
typ (Type n o) = (name n) ++ (num $ toInteger o)
-- 6 Unique prefixes.
name AFloat = [0,0,0]
name AInt = [0,0,1]
name ABool = [0,1,0]
name AVoid = [0,1,1]
name (AType n) = [1,0] ++ (num $ toInteger n)
name (ATree t) = [1,1] ++ (tree t)
-- 3 Unique prefixes
tree ANil = 
tree (AAtom t) = [1,0] ++ (typ t)
tree (ACons t1 t2) = [1,1] ++ (typ t1) ++ (typ t2)
-- Self-delimiting numbers.
num 0 = 
num n = [1, mod n 2] ++ (num $ div n 2)