[<<][compsci][>>][..]
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 [1]

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)
                  deriving (Eq,Show)

  data TypeTree   = AAtom Type
                  | ANil
                  | ACons Type Type
                  deriving (Eq,Show)

  data Type       = Type TypeName TypeOrder
                  deriving (Eq,Show)

  type TypeOrder = Int

Prime-encoded positive sequences:

  primes :: [Integer]
  primes = sieve [2..]
    where
      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 = [1]
    name AInt   = [2]
    name ABool  = [3]
    name AVoid  = [4]
    name (AType i) = [5, 1+i]
    name (ATree t) = [6] ++ tree t

    tree ANil = [1]
    tree (AAtom t) = [2] ++ typ t
    tree (ACons t1 t2) = [2] ++ typ t1 ++ typ t2

    typ (Type n o) = name n ++ [1+o]


Binary sequences:

  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          = [0]
    tree (AAtom t)     = [1,0] ++ (typ t)
    tree (ACons t1 t2) = [1,1] ++ (typ t1) ++ (typ t2)

    -- Self-delimiting numbers.
    num 0 = [0]
    num n = [1, mod n 2] ++ (num $ div n 2)




[1] http://stackoverflow.com/questions/3596502/lazy-list-of-prime-numbers





[Reply][About]
[<<][compsci][>>][..]