{"id":1754,"date":"2011-12-10T08:53:30","date_gmt":"2011-12-10T08:53:30","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1754"},"modified":"2013-03-08T05:48:58","modified_gmt":"2013-03-08T05:48:58","slug":"enumeracion-del-producto-cartesiano-de-los-naturales-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/enumeracion-del-producto-cartesiano-de-los-naturales-en-haskell\/","title":{"rendered":"Enumeraci\u00f3n del producto cartesiano de los naturales en Haskell"},"content":{"rendered":"<p>En esta relaci\u00f3n se definen funciones que enumeran el conjunto de los pares de n\u00fameros naturales; es decir, funciones biyectivas <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=f%3A+%5Cmathbb%7BN%7D+%5Cto+%5Cmathbb%7BN%7D+%5Ctimes+%5Cmathbb%7BN%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"f: &#92;mathbb{N} &#92;to &#92;mathbb{N} &#92;times &#92;mathbb{N}\" class=\"latex\" \/> y  <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=g%3A+%5Cmathbb%7BN%7D+%5Ctimes+%5Cmathbb%7BN%7D+%5Cto+%5Cmathbb%7BN%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"g: &#92;mathbb{N} &#92;times &#92;mathbb{N} &#92;to &#92;mathbb{N}\" class=\"latex\" \/>. <\/p>\n<p>Las definiciones de las funciones se hacen por comprensi\u00f3n y recursi\u00f3n. La propiedad biyectiva se comprueba mostrando que <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=f+%5Ccdot+g&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"f &#92;cdot g\" class=\"latex\" \/> y <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=g+%5Ccdot+f&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"g &#92;cdot f\" class=\"latex\" \/> son la identidad.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir, por comprensi\u00f3n, la constante\r\n--    pares :: [(Int,Int)]\r\n-- tal que pares es la lista de los pares de n\u00fameros taturales ordenados\r\n-- primero por la suma y despu\u00e9s por la primera coordenada; es decir,\r\n-- (x,y) es menor que (x',y') si x+y < x'+y' \u00f3 (x+y = x'+y' y x  < x'). \r\n-- Por ejemplo,\r\n--    ghci> take 10 pares\r\n--    [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]\r\n-- ---------------------------------------------------------------------\r\n\r\npares :: [(Int,Int)]\r\npares = [(x,z-x) | z <- [0..], x <- [0..z]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    par :: Int -> (Int,Int)\r\n-- tal que (par n) es el par de n\u00fameros naturales que ocupa la posici\u00f3n\r\n-- n en la lista pares. Por ejemplo,\r\n--    par 5  ==  (2,0)\r\n-- ---------------------------------------------------------------------\r\n\r\npar :: Int -> (Int,Int)\r\npar n = pares !! n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    par :: Int -> (Int,Int)\r\n-- tal que (par' n) es el par de n\u00fameros naturales que ocupa la posici\u00f3n\r\n-- n en la lista pares. Por ejemplo,\r\n--    par' 5  ==  (2,0)\r\n-- ---------------------------------------------------------------------\r\n\r\npar' :: Int -> (Int,Int)\r\npar' 0 = (0,0)\r\npar' (n+1) | y == 0    = (0,x+1)\r\n           | otherwise = (x+1,y-1)\r\n    where (x,y) = par' n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    equivalencia_par :: Int -> Bool\r\n-- (equivalencia_par n) se verifica si para todo n\u00famero natural x menor\r\n-- o igual que n se tiene que (par x) y (par' x) son iguales. Por\r\n-- ejemplo, \r\n--    equivalencia_par 100  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nequivalencia_par :: Int -> Bool\r\nequivalencia_par n =\r\n    and [par x == par' x | x <- [0..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, por comprensi\u00f3n, la funci\u00f3n\r\n--    indice :: (Int,Int) -> Int\r\n-- tal que (indice (x.y)) es el lugar que ocupa el par (x,y) en la lista\r\n-- pares. Por ejemplo, \r\n--    indice (2,0)  ==  5\r\n-- ---------------------------------------------------------------------\r\n\r\nindice :: (Int,Int) -> Int\r\nindice (x,y) = fst (head [(n,(u,v)) | (n,(u,v)) <- zip [0..] pares,\r\n                                      (u,v) == (x,y)])\r\n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    indice' :: (Int,Int) -> Int\r\n-- tal que (indice' (x.y)) es el lugar que ocupa el par (x,y) en la lista\r\n-- pares. Por ejemplo, \r\n--    indice' (2,0)  ==  5\r\n-- ---------------------------------------------------------------------\r\n\r\nindice' :: (Int,Int) -> Int\r\nindice' (0,0)   = 0\r\nindice' (0,y+1) = 1 + indice' (y,0)\r\nindice' (x+1,y) = 1 + indice' (x,1+y)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    menores :: (Int,Int) -> [(Int,Int)]\r\n-- tal que (menores (x,y)) es la lista de los pares de n\u00fameros naturales\r\n-- menores que (x,y) en el orden definido en el ejercicio 1. Por\r\n-- ejemplo, \r\n--    menores (2,1) == [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2)]\r\n-- ---------------------------------------------------------------------\r\n\r\nmenores :: (Int,Int) -> [(Int,Int)]\r\nmenores (x,y) = takeWhile (\/= (x,y)) pares\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    equivalencia_indice :: Int -> Bool\r\n-- (equivalencia_indice (x,y)) se verifica si para todo par de n\u00fameros\r\n-- naturales (u,v) menores que (x,y) se tiene que (indice (u,v)) es\r\n-- igual que (indice' (u,v)). Por ejemplo,\r\n--    equivalencia_indice (14,0)  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nequivalencia_indice :: (Int,Int) -> Bool\r\nequivalencia_indice (x,y) =\r\n    and [indice (u,v) == indice (u,v) | (u,v) <- menores (x,y)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la propiedad\r\n--    prop_indice_par :: Int -> Bool\r\n-- tal que (prop_indice_par n) se verifica si para todo n\u00famero natural x\r\n-- menor o igual que n se tiene que (indice (par x)) es igual a x. Por\r\n-- ejemplo, \r\n--    prop_indice_par 100  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_indice_par :: Int -> Bool\r\nprop_indice_par n =\r\n    and [indice (par x) == x | x <- [0..n]] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la propiedad\r\n--    prop_par_indice :: Int -> Bool\r\n-- tal que (prop_par_indice (x,y)) se verifica si para si para todo par\r\n-- de n\u00fameros naturales (u,v) menores que (x,y) se tiene que \r\n-- (par (indice (u,v))) es igual a (u,v). Por\r\n-- ejemplo, \r\n--    prop_par_indice (14,0)  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_par_indice :: (Int,Int) -> Bool\r\nprop_par_indice (x,y) =\r\n    and [par (indice (u,v)) == (u,v) | (u,v) <- menores (x,y)]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En esta relaci\u00f3n se definen funciones que enumeran el conjunto de los pares de n\u00fameros naturales; es decir, funciones biyectivas y . Las definiciones de las funciones se hacen por comprensi\u00f3n y recursi\u00f3n. La propiedad biyectiva se comprueba mostrando que y son la identidad.<\/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":[5],"tags":[270],"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\/1754"}],"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=1754"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1754\/revisions"}],"predecessor-version":[{"id":2890,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1754\/revisions\/2890"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1754"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1754"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1754"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}