{"id":1702,"date":"2011-11-22T16:17:07","date_gmt":"2011-11-22T16:17:07","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1702"},"modified":"2013-03-08T05:48:59","modified_gmt":"2013-03-08T05:48:59","slug":"i1m2011-ejercicios-de-definiciones-por-recursion-y-comprension-en-haskell-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-ejercicios-de-definiciones-por-recursion-y-comprension-en-haskell-1\/","title":{"rendered":"I1M2011: Ejercicios de definiciones por recursi\u00f3n y comprensi\u00f3n en Haskell (1)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones de los ejercicios de la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_7.hs\">7\u00aa relaci\u00f3n<\/a >en la que se presentan ejercicios con dos definiciones (una por recursi\u00f3n y otra por comprensi\u00f3n) y la comprobaci\u00f3n de la equivalencia de las dos definiciones con QuickCheck. Los ejercicios corresponden al <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-5.pdf\">tema 5<\/a> y al <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-6.pdf\">tema 6<\/a>.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- I1M 2011-12: Rel_7_sol.hs (17 de Noviembre de 2011)\r\n-- Definiciones por recursi\u00f3n y por comprensi\u00f3n (1)\r\n-- Departamento de Ciencias de la Computaci\u00f3n e I.A.\r\n-- Universidad de Sevilla\r\n-- =====================================================================\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.1. Definir, por recursi\u00f3n; la funci\u00f3n \r\n--    sumaCuadrados :: Integer -> Integer\r\n-- tal que (sumaCuadrados n) es la suma de los cuadrados de los n\u00fameros\r\n-- de 1 a n. Por ejemplo, \r\n--    sumaCuadrados 4  ==  30 \r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadrados :: Integer -> Integer\r\nsumaCuadrados 0     = 0\r\nsumaCuadrados (n+1) = sumaCuadrados n + (n+1)*(n+1)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.2. Comprobar con QuickCheck si sumaCuadrados n es igual a\r\n-- n(n+1)(2n+1)\/6. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_SumaCuadrados n =\r\n  n >= 0 ==>\r\n    sumaCuadrados n == n * (n+1) * (2*n+1) `div` 6  \r\n\r\n-- La comprobaci\u00f3n es\r\n--    Main> quickCheck prop_SumaCuadrados\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.3. Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    sumaCuadrados' :: Integer --> Integer\r\n-- tal que (sumaCuadrados' n) es la suma de los cuadrados de los n\u00fameros\r\n-- de 1 a n. Por ejemplo, \r\n--    sumaCuadrados' 4  ==  30 \r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadrados' :: Integer -> Integer\r\nsumaCuadrados' n = sum [x^2 | x <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.4. Comprobar con QuickCheck que las funciones\r\n-- sumaCuadrados y sumaCuadrados' son equivalentes sobre los n\u00fameros\r\n-- naturales. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_sumaCuadrados n =\r\n    n >= 0 ==> sumaCuadrados n == sumaCuadrados' n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_sumaCuadrados\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.1. Se quiere formar una escalera con bloques cuadrados,\r\n-- de forma que tenga un n\u00famero determinado de escalones. Por ejemplo,\r\n-- una escalera con tres escalones tendr\u00eda la siguiente forma:\r\n--        XX\r\n--      XXXX\r\n--    XXXXXX\r\n-- Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    numeroBloques :: Integer -> Integer    \r\n-- tal que (numeroBloques n) es el n\u00famero de bloques necesarios para\r\n-- construir una escalera con n escalones. Por ejemplo,\r\n--    numeroBloques 1   == 2\r\n--    numeroBloques 3   == 12\r\n--    numeroBloques 10  == 110\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroBloques :: Integer -> Integer    \r\nnumeroBloques 0     = 0\r\nnumeroBloques (n+1) = 2*(n+1) + numeroBloques n \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.2. Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    numeroBloques' :: Integer -> Integer    \r\n-- tal que (numeroBloques' n) es el n\u00famero de bloques necesarios para\r\n-- construir una escalera con n escalones. Por ejemplo,\r\n--    numeroBloques' 1   == 2\r\n--    numeroBloques' 3   == 12\r\n--    numeroBloques' 10  == 110\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroBloques' :: Integer -> Integer    \r\nnumeroBloques' n = sum [2*x | x <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.3. Comprobar con QuickCheck que (numeroBloques' n) es\r\n-- igual a n+n^2.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_numeroBloques n =\r\n    n >0 ==> numeroBloques' n == n+n^2\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_numeroBloques\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.1. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    sumaCuadradosImparesR :: Integer -> Integer\r\n-- tal que (sumaCuadradosImparesR n) es la suma de los cuadrados de los\r\n-- n\u00fameros impares desde 1 hasta n. \r\n--    sumaCuadradosImparesR 1  ==  1\r\n--    sumaCuadradosImparesR 7  ==  84\r\n--    sumaCuadradosImparesR 4  ==  10\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadradosImparesR :: Integer -> Integer\r\nsumaCuadradosImparesR 1 = 1\r\nsumaCuadradosImparesR n \r\n    | odd n     = n^2 + sumaCuadradosImparesR (n-1)\r\n    | otherwise = sumaCuadradosImparesR (n-1)\r\n                     \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.2. Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    sumaCuadradosImparesC :: Integer -> Integer\r\n-- tal que (sumaCuadradosImparesC n) es la suma de los cuadrados de los\r\n-- n\u00fameros impares desde 1 hasta n. \r\n--    sumaCuadradosImparesC 1  ==  1\r\n--    sumaCuadradosImparesC 7  ==  84\r\n--    sumaCuadradosImparesC 4  ==  10\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadradosImparesC :: Integer -> Integer\r\nsumaCuadradosImparesC n = sum [x^2 | x <- [1..n], odd x]\r\n\r\n-- Otra definici\u00f3n m\u00e1s simple es\r\nsumaCuadradosImparesC' :: Integer -> Integer\r\nsumaCuadradosImparesC' n = sum [x^2 | x <- [1,3..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.1. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    cifrasR :: Integer -> [Int]\r\n-- tal que (cifrasR n) es la lista de los cifras del n\u00famero n. Por\r\n-- ejemplo, \r\n--    cifrasR 320274  ==  [3,2,0,2,7,4]\r\n-- ---------------------------------------------------------------------\r\n\r\ncifrasR :: Integer -> [Integer]\r\ncifrasR n = reverse (cifrasR' n)\r\n\r\ncifrasR' n\r\n    | n < 10    = [n]\r\n    | otherwise = (n `rem` 10) : cifrasR' (n `div` 10)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.2. Definir, por comprensi\u00f3n, la funci\u00f3n\r\n--    cifras :: Integer -> [Int]\r\n-- tal que (cifras n) es la lista de los cifras del n\u00famero n. Por\r\n-- ejemplo, \r\n--    cifras 320274  ==  [3,2,0,2,7,4]\r\n-- Indicaci\u00f3n: Usar las funciones show y read.\r\n-- ---------------------------------------------------------------------\r\n\r\ncifras :: Integer -> [Integer]\r\ncifras n = [read [x] | x <- show n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.3. Comprobar con QuickCheck que las funciones cifrasR y\r\n-- cifras son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_cifras n =\r\n    n >= 0 ==> \r\n    cifrasR n == cifras n\r\n  \r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_cifras\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.1. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    sumaCifrasR :: Integer -> Integer\r\n-- tal que (sumaCifrasR n) es la suma de las cifras de n. Por ejemplo,\r\n--    sumaCifrasR 3     ==  3\r\n--    sumaCifrasR 2454  == 15\r\n--    sumaCifrasR 20045 == 11\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCifrasR :: Integer -> Integer\r\nsumaCifrasR n\r\n    | n < 10    = n\r\n    | otherwise = n `rem` 10 + sumaCifrasR (n `div` 10)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.2. Definir, sin usar recursi\u00f3n, la funci\u00f3n \r\n--    sumaCifrasNR :: Integer -> Integer\r\n-- tal que (sumaCifrasNR n) es la suma de las cifras de n. Por ejemplo,\r\n--    sumaCifrasNR 3     ==  3\r\n--    sumaCifrasNR 2454  == 15\r\n--    sumaCifrasNR 20045 == 11\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCifrasNR :: Integer -> Integer\r\nsumaCifrasNR n = sum (cifras n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.3. Comprobar con QuickCheck que las funciones sumaCifrasR\r\n-- y sumaCifrasNR son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_sumaCifras n =\r\n    n >= 0 ==>\r\n    sumaCifrasR n == sumaCifrasNR n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_sumaCifras\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n \r\n--    esCifra :: Integer -> Integer -> Bool\r\n-- tal que (esCifra x n) se verifica si x es una cifra de n. Por\r\n-- ejemplo, \r\n--    esCifra 4 1041  ==  True\r\n--    esCifra 3 1041  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesCifra :: Integer -> Integer -> Bool\r\nesCifra x n = elem x (cifras n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    numeroDeCifras :: Integer -> Integer\r\n-- tal que (numeroDeCifras x) es el n\u00famero de cifras de x. Por ejemplo,\r\n--    numeroDeCifras 34047  ==  5\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroDeCifras :: Integer -> Int\r\nnumeroDeCifras x = length (cifras x)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.1 Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    listaNumeroR :: [Integer] -> Integer\r\n-- tal que (listaNumeroR xs) es el n\u00famero formado por las cifras xs. Por\r\n-- ejemplo, \r\n--    listaNumeroR [5]        == 5\r\n--    listaNumeroR [1,3,4,7]  == 1347\r\n--    listaNumeroR [0,0,1]    == 1\r\n-- ---------------------------------------------------------------------\r\n\r\nlistaNumeroR :: [Integer] -> Integer\r\nlistaNumeroR xs = listaNumeroR' (reverse xs)\r\n\r\nlistaNumeroR' :: [Integer] -> Integer\r\nlistaNumeroR' [x]    = x\r\nlistaNumeroR' (x:xs) = x + 10 * (listaNumeroR' xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.2. Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    listaNumeroC :: [Integer] -> Integer\r\n-- tal que (listaNumeroC xs) es el n\u00famero formado por las cifras xs. Por\r\n-- ejemplo, \r\n--    listaNumeroC [5]        == 5\r\n--    listaNumeroC [1,3,4,7]  == 1347\r\n--    listaNumeroC [0,0,1]    == 1\r\n-- ---------------------------------------------------------------------\r\n\r\nlistaNumeroC :: [Integer] -> Integer\r\nlistaNumeroC xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]\r\n<\/pre>\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 de los ejercicios de la 7\u00aa relaci\u00f3nen la que se presentan ejercicios con dos definiciones (una por recursi\u00f3n y otra por comprensi\u00f3n) y la comprobaci\u00f3n de la equivalencia de las dos definiciones con QuickCheck. Los ejercicios corresponden al&#8230;<\/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":[186],"tags":[295],"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\/1702"}],"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=1702"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1702\/revisions"}],"predecessor-version":[{"id":1704,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1702\/revisions\/1704"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1702"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1702"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1702"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}