{"id":1409,"date":"2011-06-06T13:55:12","date_gmt":"2011-06-06T13:55:12","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1409"},"modified":"2011-06-13T13:56:23","modified_gmt":"2011-06-13T13:56:23","slug":"i1m2010-ejercicios-sobre-la-numeracion-de-los-racionales-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-ejercicios-sobre-la-numeracion-de-los-racionales-en-haskell\/","title":{"rendered":"I1M2010: Ejercicios sobre la numeraci\u00f3n de los racionales en Haskell"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios sobre la numeraci\u00f3n de los n\u00fameros racionales en Haskell de la 31\u00aa relaci\u00f3n<\/a>.<\/p>\n

Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El objetivo de esta relaci\u00f3n es construir dos enumeraciones de los\r\n-- n\u00fameros racionales. Concretamente, \r\n-- * una enumeraci\u00f3n basada en las representaciones hiperbinarias y\r\n-- * una enumeraci\u00f3n basada en los los \u00e1rboles de Calkin-Wilf.\r\n-- Tambi\u00e9n se incluye la comprobaci\u00f3n de la igualdad de las dos\r\n-- sucesiones y una forma alternativa de calcular el n\u00famero de\r\n-- representaciones hiperbinarias mediante la funci\u00f3n fucs.\r\n-- \r\n-- Esta relaci\u00f3n se basa en los siguientes art\u00edculos:\r\n-- * Gaussianos \"Sorpresa sumando potencias de 2\" http:\/\/goo.gl\/AHdAG\r\n-- * N. Calkin y H.S. Wilf \"Recounting the rationals\" http:\/\/goo.gl\/gVZtW\r\n-- * Wikipedia \"Calkin-Wilf tree\" http:\/\/goo.gl\/cB3vn\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\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 :: Eq a => a -> [a] -> Bool\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 && y2 == x\r\nempiezaConDos x (y1:y2:ys) = y1 == x && 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\n-- ---------------------------------------------------------------------\r\n\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
Las soluciones de las relaciones anteriores se encuentran en el libro Ejercicios de “Inform\u00e1tica de 1\u00ba de Matem\u00e1ticas” (Curso 2010-11)<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios sobre la numeraci\u00f3n de los n\u00fameros racionales en Haskell de la 31\u00aa relaci\u00f3n. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/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":[133],"tags":[287],"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\/1409"}],"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=1409"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1409\/revisions"}],"predecessor-version":[{"id":1410,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1409\/revisions\/1410"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}