'Addendum: Encoding tuples with numbers'

Posted on September 4, 2011 by phimuemue

I described how to encode tuples of natural numbers into natural numbers. Now, I wrote (hacked) a small piece in Haskell to try it in practice.

So here it is:

import Data.List
import Maybe
 
-- taken from
-- http://www.haskell.org/haskellwiki/Prime_numbers_miscellaneous#Prime_Wheels
primes = 2:3:primes'
         where
           l:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
           primes' = p : filter isPrime candidates
           isPrime n = all (not . divides n)
                       $ takeWhile (\p -> p*p <= n) primes'
           divides n p = n `mod` p == 0
 
isPrime n = all not [n `mod` p == 0 | p <- takeWhile (\p -> p*p <= n) primes]
 
ascendlist [] = []
ascendlist (h:t) = h : (ascendlist (map (+ h) t))
 
deascendlist [] = []
deascendlist (h:t) = h : map (flip (-) h) (deascendlist t)
 
encode l = encode' (ascendlist l) where
  encode' [] = 1
  encode' (h:t) = (primes !! (fromIntegral h)) * (encode' t)
 
getsprime n = if isPrime n then n else fromJust (find (\x -> n `mod` x == 0) primes)
 
decode n = deascendlist (decode' n) where
  decode' 1 = []
  decode' n = (fromIntegral pi) : (decode' (n `div` p)) where
    p = getsprime n
    pi = fromJust (findIndex (== p) primes)

The functions encode and decode do most of the work. Note that this implementation includes also the number 0 (by accident, since computers usually index lists starting with 0). However, as mentioned in the original post, it's not a very practicable solution, since we have to deal with quite large numbers and factorize them.

The program can probably be sped up by explicitly stating the types of the functions and compiling the program. I omitted them because my compiler always complained about incompatible types ([Int] and [Integer]).

The program can be tested by simply calling decode (encode [1,2,3,4,5]) or similar.