{"id":1482,"date":"2011-07-31T11:03:28","date_gmt":"2011-07-31T11:03:28","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1482"},"modified":"2011-07-31T11:03:28","modified_gmt":"2011-07-31T11:03:28","slug":"enumeraciones-de-los-numeros-racionales-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/enumeraciones-de-los-numeros-racionales-en-haskell\/","title":{"rendered":"Enumeraciones de los n\u00fameros racionales en Haskell"},"content":{"rendered":"<p>He publicado en <a href=\"https:\/\/www.glc.us.es\/~jalonso\/LogicaMente\/index.php5\/Enumeraciones_de_los_n%C3%BAmeros_racionales\">L\u00f3gicaMente<\/a> una relaci\u00f3n de ejercicios en Haskell sobre enumeraciones de los n\u00fameros racionales, cuyo contenido es el siguiente.<\/p>\n<hr width=\"100%\">\n<p>El objetivo de esta relaci\u00f3n es construir dos enumeraciones de los n\u00fameros racionales. Concretamente, <\/p>\n<ul>\n<li> una enumeraci\u00f3n basada en las representaciones hiperbinarias y\n<li> una enumeraci\u00f3n basada en los los \u00e1rboles de Calkin-Wilf.\n<\/ul>\n<p>Tambi\u00e9n se incluye la comprobaci\u00f3n de la igualdad de las dos sucesiones y una forma alternativa de calcular el n\u00famero de representaciones hiperbinarias mediante la funci\u00f3n fucs.<\/p>\n<p>Esta relaci\u00f3n se basa en los siguientes art\u00edculos:<\/p>\n<ul>\n<li> Gaussianos <a href=\"http:\/\/gaussianos.com\/sorpresa-sumando-potencias-de-2\">Sorpresa sumando potencias de 2<\/a>.\n<li> N. Calkin y H.S. Wilf <a href=\"http:\/\/www.math.clemson.edu\/~calkin\/Papers\/calkin_wilf_recounting_rationals.pdf\"> Recounting the rationals<\/a>.\n<li> Wikipedia <a href=\"http:\/\/en.wikipedia.org\/wiki\/Calkin%E2%80%93Wilf_tree\"> Calkin-Wilf tree<\/a>.\n<\/ul>\n<p>La relaci\u00f3n de ejercicios es<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Numeraci\u00f3n de los racionales mediante representaciones hiperbinarias\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la constante\r\n--    potenciasDeDos :: [Integer]\r\n-- tal que potenciasDeDos es la lista de las potencias de 2. Por\r\n-- ejemplo, \r\n--    take 10 potenciasDeDos  ==  [1,2,4,8,16,32,64,128,256,512]\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciasDeDos :: [Integer]\r\npotenciasDeDos = [2^n | n <- [0..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    empiezaConDos x (y1:y2:ys) = y1 == x &#038;&#038; y2 == x\r\n-- tal que (empiezaConDos x ys) se verifica si los dos primeros\r\n-- elementos de ys son iguales a x. Por ejemplo,\r\n--    empiezaConDos 5 [5,5,3,7]  ==  True\r\n--    empiezaConDos 5 [5,3,5,7]  ==  False\r\n--    empiezaConDos 5 [5,5,5,7]  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nempiezaConDos x (y1:y2:ys) = y1 == x &#038;&#038; y2 == x\r\nempiezaConDos x _          = False\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    representacionesHB :: Integer -> [[Integer]]\r\n-- tal que (representacionesHB n) es la lista de las representaciones\r\n-- hiperbinarias del n\u00famero n como suma de potencias de 2 donde cada\r\n-- sumando aparece como m\u00e1ximo 2 veces. Por ejemplo\r\n--    representacionesHB 5  ==  [[1,2,2],[1,4]]\r\n--    representacionesHB 6  ==  [[1,1,2,2],[1,1,4],[2,4]]\r\n-- ---------------------------------------------------------------------\r\n\r\nrepresentacionesHB :: Integer -> [[Integer]]\r\nrepresentacionesHB n = representacionesHB' n potenciasDeDos\r\nrepresentacionesHB' n (x:xs)\r\n    | n == 0    = [[]]\r\n    | x == n    = [[x]]\r\n    | x <  n    = [x:ys | ys <- representacionesHB' (n-x) (x:xs),\r\n                          not (empiezaConDos x ys)] ++\r\n                  representacionesHB' n xs\r\n    | otherwise = []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    nRepresentacionesHB :: Integer -> Integer\r\n-- tal que (nRepresentacionesHB n) es el n\u00famero de las representaciones \r\n-- hiperbinarias del n\u00famero n como suma de potencias de 2 donde cada\r\n-- sumando aparece como m\u00e1ximo 2 veces. Por ejemplo,\r\n--    ghci> [nRepresentacionesHB n | n <- [0..20]]\r\n--    [1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8]\r\n-- ---------------------------------------------------------------------\r\n\r\nnRepresentacionesHB :: Integer -> Integer\r\nnRepresentacionesHB = genericLength . representacionesHB\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    termino :: Integer -> (Integer,Integer)\r\n-- tal que (termino n) es el par formado por el n\u00famero de\r\n-- representaciones hiperbinarias de n y de n+1 (que se interpreta como \r\n-- su cociente). Por ejemplo, \r\n--    termino 4  ==  (3,2)\r\n-- ---------------------------------------------------------------------\r\n\r\ntermino :: Integer -> (Integer,Integer)\r\ntermino n = (nRepresentacionesHB n, nRepresentacionesHB (n+1))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    sucesionHB :: [(Integer,Integer)]\r\n-- sucesionHB es la la sucesi\u00f3n cuyo t\u00e9mino n-\u00e9simo es (termino n); es\r\n-- decir, el par formado por el n\u00famero de representaciones hiperbinarias\r\n-- de n y de n+1. Por ejemplo, \r\n--    ghci> take 10 sucesionHB\r\n--    [(1,1),(1,2),(2,1),(1,3),(3,2),(2,3),(3,1),(1,4),(4,3),(3,5)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionHB :: [(Integer,Integer)]\r\nsucesionHB = [termino n | n <- [0..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Comprobar con QuickCheck que, para todo n,\r\n-- (nRepresentacionesHB n) y  (nRepresentacionesHB (n+1)) son primos\r\n-- entre s\u00ed. \r\n-- ---------------------------------------------------------------------\r\n\r\nprop_irreducibles :: Integer -> Property\r\nprop_irreducibles n =\r\n    n >= 0 ==> \r\n    gcd (nRepresentacionesHB n) (nRepresentacionesHB (n+1)) == 1\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_irreducibles\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Comprobar con QuickCheck que todos los elementos de la\r\n-- sucesionHB son distintos.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_distintos :: Integer -> Integer -> Bool\r\nprop_distintos n m =\r\n    termino n' \/= termino m'\r\n    where n' = abs n\r\n          m' = n' + abs m + 1\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_distintos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la funci\u00f3n\r\n--    contenido :: Integer -> Integer -> Bool\r\n-- tal que (contenido n) se verifica si la expresiones reducidas de\r\n-- todas las fracciones x\/y, con x e y entre 1 y n, pertenecen a la\r\n-- sucesionHB. Por ejemplo,  \r\n--    contenidos 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\ncontenido :: Integer -> Bool\r\ncontenido n =\r\n    and [pertenece (reducida (x,y)) sucesionHB |\r\n         x <- [1..n], y <- [1..n]]\r\n    where pertenece x (y:ys) = x == y || pertenece x ys\r\n          reducida (x,y) = (x `div` z, y `div` z)\r\n              where z = gcd x y\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    indice :: (Integer,Integer) -> Integer\r\n-- tal que (indice (a,b)) es el \u00edndice del par (a,b) en la sucesi\u00f3n de\r\n-- los racionales. Por ejemplo, \r\n--    indice (3,2)  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nindice :: (Integer,Integer) -> Integer\r\nindice (a,b) = head [n | (n,(x,y)) <- zip [0..] sucesionHB, \r\n                         (x,y) == (a,b)] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Numeraciones mediante \u00e1rboles de Calkin-Wilf                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El \u00e1rbol de Calkin-Wilf es el \u00e1rbol definido por las siguientes\r\n-- reglas:\r\n--    * El nodo ra\u00edz es el (1,1)\r\n--    * Los hijos del nodo (x,y) son (x,x+y) y (x+y,y)\r\n-- Por ejemplo, los 4 primeros niveles del \u00e1rbol de Calkin-Wilf son \r\n--                         (1,1)\r\n--                           |\r\n--               +-----------+-----------+\r\n--               |                       |\r\n--             (1,2)                   (2,1)\r\n--               |                       |\r\n--         +-----+-----+           +-----+-----+\r\n--         |           |           |           |\r\n--       (1,3)       (3,2)       (2,3)       (3,1)\r\n--         |           |           |           |         \r\n--      +--+--+     +--+--+     +--+--+     +--+--+\r\n--      |     |     |     |     |     |     |     | \r\n--    (1,4) (4,3) (3,5) (5,2) (2,5) (5,3) (3,4) (4,1)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n \r\n--    sucesores :: (Integer,Integer) -> [(Integer,Integer)]\r\n-- tal que (sucesores (x,y)) es la lista de los hijos del par (x,y) en\r\n-- el \u00e1rbol de Calkin-Wilf. Por ejemplo, \r\n--    sucesores (3,2)  ==  [(3,5),(5,2)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesores :: (Integer,Integer) -> [(Integer,Integer)]\r\nsucesores (x,y) = [(x,x+y),(x+y,y)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    siguiente :: [(Integer,Integer)] -> [(Integer,Integer)]\r\n-- tal que (siguiente xs) es la lista formada por los hijos de los\r\n-- elementos de xs en el \u00e1rbol de Calkin-Wilf. Por ejemplo, \r\n--    ghci> siguiente [(1,3),(3,2),(2,3),(3,1)]\r\n--    [(1,4),(4,3),(3,5),(5,2),(2,5),(5,3),(3,4),(4,1)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsiguiente :: [(Integer,Integer)] -> [(Integer,Integer)]\r\nsiguiente xs = [p | x <- xs, p <- sucesores x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la constante\r\n--    nivelesCalkinWilf:: [[(Integer,Integer)]]\r\n-- tal que nivelesCalkinWilf es la lista de los niveles del \u00e1rbol de\r\n-- Calkin-Wilf. Por ejemplo, \r\n--    ghci> take 4 nivelesCalkinWilf\r\n--    [[(1,1)],\r\n--     [(1,2),(2,1)],\r\n--     [(1,3),(3,2),(2,3),(3,1)],\r\n--     [(1,4),(4,3),(3,5),(5,2),(2,5),(5,3),(3,4),(4,1)]]\r\nnivelesCalkinWilf:: [[(Integer,Integer)]]\r\nnivelesCalkinWilf = iterate siguiente [(1,1)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la constante \r\n--    sucesionCalkinWilf :: [(Integer,Integer)]\r\n-- tal que sucesionCalkinWilf es la lista correspondiente al recorrido\r\n-- en anchura del \u00e1rbol de Calkin-Wilf. Por ejemplo,\r\n--    ghci> take 10 sucesionCalkinWilf\r\n--    [(1,1),(1,2),(2,1),(1,3),(3,2),(2,3),(3,1),(1,4),(4,3),(3,5)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionCalkinWilf :: [(Integer,Integer)]\r\nsucesionCalkinWilf = concat nivelesCalkinWilf\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir la funci\u00f3n\r\n--    igual_sucesion_HB_CalkinWilf :: Int -> Bool\r\n-- tal que (igual_sucesion_HB_CalkinWilf n) se verifica si los n\r\n-- primeros t\u00e9rminos de la sucesi\u00f3n HB son iguales que los de la\r\n-- sucesi\u00f3n de Calkin-Wilf. Por ejemplo,\r\n--    igual_sucesion_HB_CalkinWilf 20  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nigual_sucesion_HB_CalkinWilf :: Int -> Bool\r\nigual_sucesion_HB_CalkinWilf n =\r\n    take n sucesionCalkinWilf == take n sucesionHB\r\n\r\n-- ---------------------------------------------------------------------\r\n-- N\u00famero de representaciones hiperbinarias mediante la funci\u00f3n fusc\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la funci\u00f3n\r\n--    fusc :: Integer -> Integer\r\n-- tal que \r\n--    fusc(0)    = 1\r\n--    fusc(2n+1) = fusc(n)\r\n--    fusc(2n+2) = fusc(n+1)+fusc(n)\r\n-- Por ejemplo,\r\n--    fusc 4  ==  3\r\n-- ---------------------------------------------------------------------\r\n\r\nfusc :: Integer -> Integer\r\nfusc 0 = 1\r\nfusc  n | odd n     = fusc ((n-1) `div` 2)\r\n        | otherwise = fusc(m+1) + fusc m\r\n                      where m = (n-2) `div` 2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Comprobar con QuickCheck que, para todo n, (fusc n) es\r\n-- el n\u00famero de las representaciones hiperbinarias del n\u00famero n como\r\n-- suma de potencias de 2 donde cada sumando aparece como m\u00e1ximo 2\r\n-- veces; es decir, que las funciones fusc y nRepresentacionesHB son\r\n-- equivalentes. \r\n-- ---------------------------------------------------------------------\r\n\r\nprop_fusc :: Integer -> Bool\r\nprop_fusc n = nRepresentacionesHB n' == fusc n'\r\n              where n' = abs n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_fusc\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>He publicado en L\u00f3gicaMente una relaci\u00f3n de ejercicios en Haskell sobre enumeraciones de los n\u00fameros racionales, cuyo contenido es el siguiente. El objetivo de esta relaci\u00f3n es construir dos enumeraciones de los n\u00fameros racionales. Concretamente, una enumeraci\u00f3n basada en las representaciones hiperbinarias y una enumeraci\u00f3n basada en los los \u00e1rboles de Calkin-Wilf. Tambi\u00e9n se incluye&#8230;<\/p>\n","protected":false},"author":2,"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":[5],"tags":[270,126],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1482"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1482"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1482\/revisions"}],"predecessor-version":[{"id":1487,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1482\/revisions\/1487"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1482"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1482"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1482"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}