Codificación de Gödel
Dada una lista de números naturales xs, la codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificación de xs es
2^6 * 3^0 * 5^4 = 64 * 1 * 625 = 40000.
Definir las funciones
codificaG :: [Integer] -> Integer decodificaG :: Integer -> [Integer]
tales que
- (codificaG xs) es la codificación de Gödel de xs. Por ejemplo,
codificaG [6,0,4] == 40000 codificaG [3,1,1] == 120 codificaG [3,1,0,0,0,0,0,1] == 456 codificaG [1..6] == 4199506113235182750
- (decodificaG n) es la lista xs cuya codificación es n. Por ejemplo,
decodificaG 40000 == [6,0,4] decodificaG 120 == [3,1,1] decodificaG 456 == [3,1,0,0,0,0,0,1] decodificaG 4199506113235182750 == [1,2,3,4,5,6]
Comprobar con QuickCheck que ambas funciones son inversas.
Soluciones
import Data.List (genericLength, group) import Data.Numbers.Primes (primes, primeFactors) import Test.QuickCheck codificaG :: [Integer] -> Integer codificaG xs = product (zipWith (^) primes xs) decodificaG :: Integer -> [Integer] decodificaG n = aux ps zs where ps = [(head xs, genericLength xs) | xs <- group $ primeFactors n] (z,_) = last ps zs = takeWhile (<= z) primes aux [] ys = [] aux us@((p,l):xs) (y:ys) | p > y = 0:aux us ys | p == y = l:aux xs ys | otherwise = 0:aux xs ys -- Las propiedades son propCodifica1 :: [Integer] -> Bool propCodifica1 xs = decodificaG (codificaG ys) == ys where ys = map ((+1) . abs) xs propCodifica2 :: Integer -> Property propCodifica2 n = n > 0 ==> codificaG (decodificaG n) == n -- Las comprobaciones son -- λ> quickCheck propCodifica1 -- +++ OK, passed 100 tests. -- -- λ> quickCheck propCodifica2 -- +++ OK, passed 100 tests.