{"id":5328,"date":"2016-02-26T16:25:38","date_gmt":"2016-02-26T15:25:38","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5328"},"modified":"2016-02-29T10:31:01","modified_gmt":"2016-02-29T09:31:01","slug":"i1m2015-ejercicios-sobre-la-numeracion-de-los-racionales-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-ejercicios-sobre-la-numeracion-de-los-racionales-en-haskell\/","title":{"rendered":"I1M2015: Ejercicios sobre la numeraci\u00f3n de los racionales en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">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 relaci\u00f3n 22.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es construir dos enumeraciones de los\n-- n\u00fameros racionales. Concretamente, \n-- * una enumeraci\u00f3n basada en las representaciones hiperbinarias y\n-- * una enumeraci\u00f3n basada en los los \u00e1rboles de Calkin-Wilf.\n-- Tambi\u00e9n se incluye la comprobaci\u00f3n de la igualdad de las dos\n-- sucesiones y una forma alternativa de calcular el n\u00famero de\n-- representaciones hiperbinarias mediante la funci\u00f3n fucs.\n-- \n-- Esta relaci\u00f3n se basa en los siguientes art\u00edculos:\n-- * Gaussianos \"Sorpresa sumando potencias de 2\" http:\/\/goo.gl\/AHdAG\n-- * N. Calkin y H.S. Wilf \"Recounting the rationals\" http:\/\/goo.gl\/gVZtW\n-- * Wikipedia \"Calkin-Wilf tree\" http:\/\/goo.gl\/cB3vn\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\nimport Data.List\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Numeraci\u00f3n de los racionales mediante representaciones hiperbinarias\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la constante\n--    potenciasDeDos :: [Integer]\n-- tal que potenciasDeDos es la lista de las potencias de 2. Por\n-- ejemplo, \n--    take 10 potenciasDeDos  ==  [1,2,4,8,16,32,64,128,256,512]\n-- ---------------------------------------------------------------------\n\npotenciasDeDos :: [Integer]\npotenciasDeDos = [2^n | n <- [0..]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    empiezaConDos :: Eq a => a -> [a] -> Bool\n-- tal que (empiezaConDos x ys) se verifica si los dos primeros\n-- elementos de ys son iguales a x. Por ejemplo,\n--    empiezaConDos 5 [5,5,3,7]  ==  True\n--    empiezaConDos 5 [5,3,5,7]  ==  False\n--    empiezaConDos 5 [5,5,5,7]  ==  True\n-- ---------------------------------------------------------------------\n\nempiezaConDos x (y1:y2:ys) = y1 == x && y2 == x\nempiezaConDos x (y1:y2:ys) = y1 == x && y2 == x\nempiezaConDos x _          = False\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    representacionesHB :: Integer -> [[Integer]]\n-- tal que (representacionesHB n) es la lista de las representaciones\n-- hiperbinarias del n\u00famero n como suma de potencias de 2 donde cada\n-- sumando aparece como m\u00e1ximo 2 veces. Por ejemplo\n--    representacionesHB 5  ==  [[1,2,2],[1,4]]\n--    representacionesHB 6  ==  [[1,1,2,2],[1,1,4],[2,4]]\n-- ---------------------------------------------------------------------\n\nrepresentacionesHB :: Integer -> [[Integer]]\nrepresentacionesHB n = aux n potenciasDeDos\naux n (x:xs)\n    | n == 0    = [[]]\n    | x == n    = [[x]]\n    | x <  n    = [x:ys | ys <- aux (n-x) (x:xs),\n                          not (empiezaConDos x ys)] ++\n                  aux n xs\n    | otherwise = []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    nRepresentacionesHB :: Integer -> Integer\n-- tal que (nRepresentacionesHB n) es el n\u00famero de las representaciones \n-- hiperbinarias del n\u00famero n como suma de potencias de 2 donde cada\n-- sumando aparece como m\u00e1ximo 2 veces. Por ejemplo,\n--    ghci> [nRepresentacionesHB n | n <- [0..20]]\n--    [1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8]\n-- ---------------------------------------------------------------------\n\nnRepresentacionesHB :: Integer -> Integer\nnRepresentacionesHB = genericLength . representacionesHB\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    termino :: Integer -> (Integer,Integer)\n-- tal que (termino n) es el par formado por el n\u00famero de\n-- representaciones hiperbinarias de n y de n+1 (que se interpreta como \n-- su cociente). Por ejemplo, \n--    termino 4  ==  (3,2)\n-- ---------------------------------------------------------------------\n\ntermino :: Integer -> (Integer,Integer)\ntermino n = (nRepresentacionesHB n, nRepresentacionesHB (n+1))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    sucesionHB :: [(Integer,Integer)]\n-- sucesionHB es la la sucesi\u00f3n cuyo t\u00e9mino n-\u00e9simo es (termino n); es\n-- decir, el par formado por el n\u00famero de representaciones hiperbinarias\n-- de n y de n+1. Por ejemplo, \n--    ghci> take 10 sucesionHB\n--    [(1,1),(1,2),(2,1),(1,3),(3,2),(2,3),(3,1),(1,4),(4,3),(3,5)]\n-- ---------------------------------------------------------------------\n\nsucesionHB :: [(Integer,Integer)]\nsucesionHB = [termino n | n <- [0..]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Comprobar con QuickCheck que, para todo n,\n-- (nRepresentacionesHB n) y  (nRepresentacionesHB (n+1)) son primos\n-- entre s\u00ed. \n-- ---------------------------------------------------------------------\n\nprop_irreducibles :: Integer -> Property\nprop_irreducibles n =\n    n >= 0 ==> \n    gcd (nRepresentacionesHB n) (nRepresentacionesHB (n+1)) == 1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_irreducibles\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Comprobar con QuickCheck que todos los elementos de la\n-- sucesionHB son distintos.\n-- ---------------------------------------------------------------------\n\nprop_distintos :: Integer -> Integer -> Bool\nprop_distintos n m =\n    termino n1 \/= termino m1\n    where n1 = abs n\n          m1 = n1 + abs m + 1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_distintos\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    contenido :: Integer -> Integer -> Bool\n-- tal que (contenido n) se verifica si la expresiones reducidas de\n-- todas las fracciones x\/y, con x e y entre 1 y n, pertenecen a la\n-- sucesionHB. Por ejemplo,  \n--    contenidos 5  ==  True\n-- ---------------------------------------------------------------------\n\ncontenido :: Integer -> Bool\ncontenido n =\n    and [pertenece (reducida (x,y)) sucesionHB |\n         x <- [1..n], y <- [1..n]]\n    where pertenece x (y:ys) = x == y || pertenece x ys\n          reducida (x,y) = (x `div` z, y `div` z)\n              where z = gcd x y\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    indice :: (Integer,Integer) -> Integer\n-- tal que (indice (a,b)) es el \u00edndice del par (a,b) en la sucesi\u00f3n de\n-- los racionales. Por ejemplo, \n--    indice (3,2)  ==  4\n-- ---------------------------------------------------------------------\n\nindice :: (Integer,Integer) -> Integer\nindice (a,b) = head [n | (n,(x,y)) <- zip [0..] sucesionHB, \n                         (x,y) == (a,b)] \n\n-- ---------------------------------------------------------------------\n-- Numeraciones mediante \u00e1rboles de Calkin-Wilf                       --\n-- ---------------------------------------------------------------------\n\n-- El \u00e1rbol de Calkin-Wilf es el \u00e1rbol definido por las siguientes\n-- reglas:\n--    * El nodo ra\u00edz es el (1,1)\n--    * Los hijos del nodo (x,y) son (x,x+y) y (x+y,y)\n-- Por ejemplo, los 4 primeros niveles del \u00e1rbol de Calkin-Wilf son \n--                         (1,1)\n--                           |\n--               +-----------+-----------+\n--               |                       |\n--             (1,2)                   (2,1)\n--               |                       |\n--         +-----+-----+           +-----+-----+\n--         |           |           |           |\n--       (1,3)       (3,2)       (2,3)       (3,1)\n--         |           |           |           |         \n--      +--+--+     +--+--+     +--+--+     +--+--+\n--      |     |     |     |     |     |     |     | \n--    (1,4) (4,3) (3,5) (5,2) (2,5) (5,3) (3,4) (4,1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n \n--    sucesores :: (Integer,Integer) -> [(Integer,Integer)]\n-- tal que (sucesores (x,y)) es la lista de los hijos del par (x,y) en\n-- el \u00e1rbol de Calkin-Wilf. Por ejemplo, \n--    sucesores (3,2)  ==  [(3,5),(5,2)]\n-- ---------------------------------------------------------------------\n\nsucesores :: (Integer,Integer) -> [(Integer,Integer)]\nsucesores (x,y) = [(x,x+y),(x+y,y)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    siguiente :: [(Integer,Integer)] -> [(Integer,Integer)]\n-- tal que (siguiente xs) es la lista formada por los hijos de los\n-- elementos de xs en el \u00e1rbol de Calkin-Wilf. Por ejemplo, \n--    ghci> siguiente [(1,3),(3,2),(2,3),(3,1)]\n--    [(1,4),(4,3),(3,5),(5,2),(2,5),(5,3),(3,4),(4,1)]\n-- ---------------------------------------------------------------------\n\nsiguiente :: [(Integer,Integer)] -> [(Integer,Integer)]\nsiguiente xs = [p | x <- xs, p <- sucesores x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la constante\n--    nivelesCalkinWilf:: [[(Integer,Integer)]]\n-- tal que nivelesCalkinWilf es la lista de los niveles del \u00e1rbol de\n-- Calkin-Wilf. Por ejemplo, \n--    ghci> take 4 nivelesCalkinWilf\n--    [[(1,1)],\n--     [(1,2),(2,1)],\n--     [(1,3),(3,2),(2,3),(3,1)],\n--     [(1,4),(4,3),(3,5),(5,2),(2,5),(5,3),(3,4),(4,1)]]\n-- ---------------------------------------------------------------------\n\nnivelesCalkinWilf:: [[(Integer,Integer)]]\nnivelesCalkinWilf = iterate siguiente [(1,1)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la constante \n--    sucesionCalkinWilf :: [(Integer,Integer)]\n-- tal que sucesionCalkinWilf es la lista correspondiente al recorrido\n-- en anchura del \u00e1rbol de Calkin-Wilf. Por ejemplo,\n--    ghci> take 10 sucesionCalkinWilf\n--    [(1,1),(1,2),(2,1),(1,3),(3,2),(2,3),(3,1),(1,4),(4,3),(3,5)]\n-- ---------------------------------------------------------------------\n\nsucesionCalkinWilf :: [(Integer,Integer)]\nsucesionCalkinWilf = concat nivelesCalkinWilf\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    igual_sucesion_HB_CalkinWilf :: Int -> Bool\n-- tal que (igual_sucesion_HB_CalkinWilf n) se verifica si los n\n-- primeros t\u00e9rminos de la sucesi\u00f3n HB son iguales que los de la\n-- sucesi\u00f3n de Calkin-Wilf. Por ejemplo,\n--    igual_sucesion_HB_CalkinWilf 20  ==  True\n-- ---------------------------------------------------------------------\n\nigual_sucesion_HB_CalkinWilf :: Int -> Bool\nigual_sucesion_HB_CalkinWilf n =\n    take n sucesionCalkinWilf == take n sucesionHB\n\n-- ---------------------------------------------------------------------\n-- N\u00famero de representaciones hiperbinarias mediante la funci\u00f3n fusc\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    fusc :: Integer -> Integer\n-- tal que \n--    fusc(0)    = 1\n--    fusc(2n+1) = fusc(n)\n--    fusc(2n+2) = fusc(n+1)+fusc(n)\n-- Por ejemplo,\n--    fusc 4  ==  3\n-- ---------------------------------------------------------------------\n\nfusc :: Integer -> Integer\nfusc 0 = 1\nfusc  n | odd n     = fusc ((n-1) `div` 2)\n        | otherwise = fusc(m+1) + fusc m\n                      where m = (n-2) `div` 2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Comprobar con QuickCheck que, para todo n, (fusc n) es\n-- el n\u00famero de las representaciones hiperbinarias del n\u00famero n como\n-- suma de potencias de 2 donde cada sumando aparece como m\u00e1ximo 2\n-- veces; es decir, que las funciones fusc y nRepresentacionesHB son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\nprop_fusc :: Integer -> Bool\nprop_fusc n = nRepresentacionesHB n1 == fusc n1\n    where n1 = abs n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_fusc\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo anterior se encuentra tambi\u00e9n en <a href=\"https:\/\/github.com\/jaalonso\/I1M-Ejercicios\/blob\/master\/Ejercicios\/Rel_22_sol.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 relaci\u00f3n 22. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[250],"tags":[270,310],"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\/5328"}],"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=5328"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5328\/revisions"}],"predecessor-version":[{"id":5330,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5328\/revisions\/5330"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5328"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5328"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5328"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}