# Addendum: Encoding tuples with numbers

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.