# Addendum: Encoding tuples with numbers

Posted on 2014 03 21 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
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.