{"id":7076,"date":"2022-06-08T06:00:16","date_gmt":"2022-06-08T04:00:16","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7076"},"modified":"2022-06-05T11:16:19","modified_gmt":"2022-06-05T09:16:19","slug":"codificacion-de-godel","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/codificacion-de-godel\/","title":{"rendered":"Codificaci\u00f3n de G\u00f6del"},"content":{"rendered":"<p>Dada una lista de n\u00fameros naturales xs,  <a href=\"http:\/\/bit.ly\/2FOzmW1\">codificaci\u00f3n de G\u00f6del<\/a> de xs se obtiene multiplicando las potencias de los primos sucesivos,  siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificaci\u00f3n de xs es<\/p>\n<pre lang=\"text\">\n   2^7 * 3^1 * 5^5 = 1200000\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   codificaG   :: [Integer] -> Integer\n   decodificaG :: Integer -> [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>(codificaG xs)<\/code> es la codificaci\u00f3n de G\u00f6del de <code>xs<\/code>. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     codificaG [6,0,4]            ==  1200000\n     codificaG [3,1,1]            ==  3600\n     codificaG [3,1,0,0,0,0,0,1]  ==  4423058640\n     codificaG [1..6]             ==  126111168580452537982500\n<\/pre>\n<ul>\n<li><code>(decodificaG n)<\/code> es la lista xs cuya codificaci\u00f3n es <code>n<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     decodificaG 1200000                   ==  [6,0,4]\n     decodificaG 3600                      ==  [3,1,1]\n     decodificaG 4423058640                ==  [3,1,0,0,0,0,0,1]\n     decodificaG 126111168580452537982500  ==  [1,2,3,4,5,6]\n<\/pre>\n<p>Comprobar con QuickCheck que ambas funciones son inversas; es decir,<\/p>\n<pre lang=\"text\">\n   decodificaG (codificaG xs) = xs\n   codificaG (decodificaG n) = n\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primes, primeFactors)\nimport Test.QuickCheck (NonNegative (getNonNegative),\n                        NonEmptyList (NonEmpty),\n                        Positive (Positive, getPositive), quickCheck)\n\n-- 1\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG1 :: [Integer] -> Integer\ncodificaG1 = codificaG1' . codificaAux\n\ncodificaAux :: [Integer] -> [Integer]\ncodificaAux = map succ\n\ncodificaG1' :: [Integer] -> Integer\ncodificaG1' = aux primes\n  where aux _ []          = 1\n        aux (p:ps) (x:xs) = p^x * aux ps xs\n\n-- 2\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG2 :: [Integer] -> Integer\ncodificaG2 = codificaG2' . codificaAux\n\ncodificaG2' :: [Integer] -> Integer\ncodificaG2' xs = product [p^x | (p, x) <- zip primes xs]\n\n-- 3\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG3 :: [Integer] -> Integer\ncodificaG3 = codificaG3' . codificaAux\n\ncodificaG3' :: [Integer] -> Integer\ncodificaG3' xs = product (zipWith (^) primes xs)\n\n-- 4\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG4 :: [Integer] -> Integer\ncodificaG4 = codificaG4' . codificaAux\n\ncodificaG4' :: [Integer] -> Integer\ncodificaG4' = product . zipWith (^) primes\n\n-- Comprobaci\u00f3n de equivalencia de codificaG\n-- =========================================\n\n-- La propiedad es\nprop_codificaG :: [NonNegative Integer] -> Bool\nprop_codificaG xs =\n  all (== codificaG1 ys)\n      [codificaG2 ys,\n       codificaG3 ys,\n       codificaG4 ys]\n  where ys = map getNonNegative xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_codificaG\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de codificaG\n-- ======================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (codificaG1 (replicate (4*10^4) 1)))\n--    208100\n--    (1.73 secs, 2,312,100,136 bytes)\n--    \u03bb> length (show (codificaG2 (replicate (4*10^4) 1)))\n--    208100\n--    (1.63 secs, 2,327,676,832 bytes)\n--    \u03bb> length (show (codificaG3 (replicate (4*10^4) 1)))\n--    208100\n--    (1.62 secs, 2,323,836,832 bytes)\n--    \u03bb> length (show (codificaG4 (replicate (4*10^4) 1)))\n--    208100\n--    (1.54 secs, 2,147,635,680 bytes)\n\n-- Definici\u00f3n de codificaG\n-- =======================\n\n-- Usaremos la 4\u00aa\ncodificaG :: [Integer] -> Integer\ncodificaG = codificaG4\n\n-- Definici\u00f3n de decodificaG\n-- =========================\n\ndecodificaG :: Integer -> [Integer]\ndecodificaG = decodificaAux . decodificaG'\n\ndecodificaAux :: [Integer] -> [Integer]\ndecodificaAux = map pred\n\ndecodificaG' :: Integer -> [Integer]\ndecodificaG' 1 = [0]\ndecodificaG' n = aux primes (group (primeFactors n))\n  where aux _ [] = []\n        aux (x:xs) ((y:ys):yss) | x == y    = 1 + genericLength ys : aux xs yss\n                                | otherwise = 0 : aux xs ((y:ys):yss)\n\n-- Comprobaci\u00f3n de propiedades\n-- ===========================\n\n-- La primera propiedad es\nprop_decodificaG_codificaG :: NonEmptyList (NonNegative Integer) -> Bool\nprop_decodificaG_codificaG (NonEmpty xs) = \n  decodificaG (codificaG ys) == ys\n  where ys = map getNonNegative xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_decodificaG_codificaG\n--    +++ OK, passed 100 tests.\n\n-- La 2\u00aa propiedad es\nprop_codificaG_decodificaG :: Positive Integer -> Bool\nprop_codificaG_decodificaG (Positive n) = \n  codificaG (decodificaG n) == n\n\n-- la comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_codificaG_decodificaG\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Codificacion_de_Godel.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dada una lista de n\u00fameros naturales xs, codificaci\u00f3n de G\u00f6del de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificaci\u00f3n de xs es 2^7 * 3^1 * 5^5 = 1200000 Definir las funciones codificaG :: [Integer]&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[574,575],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7076"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7076"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7076\/revisions"}],"predecessor-version":[{"id":7077,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7076\/revisions\/7077"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}