{"id":5138,"date":"2015-10-30T20:34:26","date_gmt":"2015-10-30T19:34:26","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5138"},"modified":"2015-10-30T20:34:26","modified_gmt":"2015-10-30T19:34:26","slug":"i1m2015-ejercicios-sobre-cadenas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-ejercicios-sobre-cadenas-en-haskell\/","title":{"rendered":"I1M2015: Ejercicios sobre cadenas en Haskell"},"content":{"rendered":"<p>En la primera parte de 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 de los ejercicios de la 6\u00aa relaci\u00f3n que trata de funciones sobre cadenas.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\n-- ---------------------------------------------------------------------\n\nimport Data.Char\nimport Data.List\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    sumaDigitosC :: String -> Int\n-- tal que (sumaDigitosC xs) es la suma de los d\u00edgitos de la cadena\n-- xs. Por ejemplo, \n--    sumaDigitosC \"SE 2431 X\"  ==  10\n-- Nota: Usar las funciones (isDigit c) que se verifica si el car\u00e1cter c\n-- es un d\u00edgito y (digitToInt d) que es el entero correspondiente al\n-- d\u00edgito d.\n-- ---------------------------------------------------------------------\n\nsumaDigitosC :: String -> Int\nsumaDigitosC xs = sum [digitToInt x | x <- xs, isDigit x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    sumaDigitosR :: String -> Int\n-- tal que (sumaDigitosR xs) es la suma de los d\u00edgitos de la cadena\n-- xs. Por ejemplo, \n--    sumaDigitosR \"SE 2431 X\"  ==  10\n-- Nota: Usar las funciones isDigit y digitToInt.\n-- ---------------------------------------------------------------------\n\nsumaDigitosR :: String -> Int\nsumaDigitosR [] = 0\nsumaDigitosR (x:xs) \n    | isDigit x  = digitToInt x + sumaDigitosR xs\n    | otherwise  = sumaDigitosR xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Comprobar con QuickCheck que ambas definiciones son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_sumaDigitosC :: String -> Bool\nprop_sumaDigitosC xs = \n    sumaDigitosC xs == sumaDigitosR xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_sumaDigitos\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    mayusculaInicial :: String -> String\n-- tal que (mayusculaInicial xs) es la palabra xs con la letra inicial\n-- en may\u00fascula y las restantes en min\u00fasculas. Por ejemplo, \n--    mayusculaInicial \"sEviLLa\"  ==  \"Sevilla\"\n--    mayusculaInicial \"\"         ==  \"\"\n-- Nota: Usar las funciones (toLower c) que es el car\u00e1cter c en\n-- min\u00fascula y (toUpper c) que es el car\u00e1cter c en may\u00fascula.\n-- ---------------------------------------------------------------------\n\nmayusculaInicial :: String -> String\nmayusculaInicial []     = []\nmayusculaInicial (x:xs) = toUpper x : [toLower x | x <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    mayusculaInicialRec :: String -> String\n-- tal que (mayusculaInicialRec xs) es la palabra xs con la letra\n-- inicial en may\u00fascula y las restantes en min\u00fasculas. Por ejemplo,\n--    mayusculaInicialRec \"sEviLLa\"  ==  \"Sevilla\"\n-- ---------------------------------------------------------------------\n\nmayusculaInicialRec :: String -> String\nmayusculaInicialRec [] = []\nmayusculaInicialRec (x:xs) = toUpper x : aux xs\n    where aux (x:xs) = toLower x : aux xs\n          aux []     = []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.3. Comprobar con QuickCheck que ambas definiciones son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_mayusculaInicial :: String -> Bool\nprop_mayusculaInicial xs = \n    mayusculaInicial xs == mayusculaInicialRec xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_mayusculaInicial\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Se consideran las siguientes reglas de may\u00fasculas\n-- iniciales para los t\u00edtulos: \n--    * la primera palabra comienza en may\u00fascula y\n--    * todas las palabras que tienen 4 letras como m\u00ednimo empiezan\n--      con may\u00fasculas\n-- Definir, por comprensi\u00f3n, la funci\u00f3n\n--    titulo :: [String] -> [String]\n-- tal que (titulo ps) es la lista de las palabras de ps con\n-- las reglas de may\u00fasculas iniciales de los t\u00edtulos. Por ejemplo,\n--    ghci> titulo [\"eL\",\"arTE\",\"DE\",\"La\",\"proGraMacion\"]\n--    [\"El\",\"Arte\",\"de\",\"la\",\"Programacion\"]\n-- ---------------------------------------------------------------------\n\ntitulo :: [String] -> [String]\ntitulo []     = []\ntitulo (p:ps) = mayusculaInicial p : [transforma p | p <- ps]\n\n-- (transforma p) es la palabra p con may\u00fascula inicial si su longitud\n-- es mayor o igual que 4 y es p en min\u00fascula en caso contrario\ntransforma :: String -> String\ntransforma p | length p >= 4 = mayusculaInicial p\n             | otherwise     = minuscula p\n\n-- (minuscula xs) es la palabra xs en min\u00fascula.\nminuscula :: String -> String\nminuscula xs = [toLower x | x <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    tituloRec :: [String] -> [String]\n-- tal que (tituloRec ps) es la lista de las palabras de ps con\n-- las reglas de may\u00fasculas iniciales de los t\u00edtulos. Por ejemplo,\n--    ghci> tituloRec [\"eL\",\"arTE\",\"DE\",\"La\",\"proGraMacion\"]\n--    [\"El\",\"Arte\",\"de\",\"la\",\"Programacion\"]\n-- ---------------------------------------------------------------------\n\ntituloRec :: [String] -> [String]\ntituloRec []     = []\ntituloRec (p:ps) = mayusculaInicial p : tituloRecAux ps\n    where tituloRecAux []     = []\n          tituloRecAux (p:ps) = transforma p : tituloRecAux ps\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.3. Comprobar con QuickCheck que ambas definiciones son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_titulo :: [String] -> Bool\nprop_titulo xs = titulo xs == tituloRec xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_titulo\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    buscaCrucigrama :: Char -> Int -> Int -> [String] -> [String]\n-- tal que (buscaCrucigrama l pos lon ps) es la lista de las palabras de\n-- la lista de palabras ps que tienen longitud lon y poseen la letra l en\n-- la posici\u00f3n pos (comenzando en 0). Por ejemplo,\n--    ghci> buscaCrucigrama 'c' 1 7 [\"ocaso\", \"casa\", \"ocupado\"]\n--    [\"ocupado\"]\n--    ghci> buscaCrucigrama 'o' 4 5 [\"ocaso\", \"casa\", \"ocupado\"]\n--    [\"ocaso\"]\n--    ghci> buscaCrucigrama 'c' (-1) 7 [\"ocaso\", \"casa\", \"ocupado\"]\n--    []\n-- ---------------------------------------------------------------------\n\nbuscaCrucigrama :: Char -> Int -> Int -> [String] -> [String]\nbuscaCrucigrama l pos lon ps =\n    [p | p <- ps,  \n         length p == lon, \n         0 <= pos,  pos < length p, \n         p !! pos == l]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    buscaCrucigramaR :: Char -> Int -> Int -> [String] -> [String]\n-- tal que (buscaCrucigramaR l pos lon ps) es la lista de las palabras\n-- de la lista de palabras ps que tienn longitud lon y posen la letra l\n-- en la posici\u00f3n pos (comenzando en 0). Por ejemplo,\n--    ghci> buscaCrucigramaR 'c' 1 7 [\"ocaso\", \"acabado\", \"ocupado\"]\n--    [\"acabado\",\"ocupado\"]\n-- ---------------------------------------------------------------------\n\nbuscaCrucigramaR :: Char -> Int -> Int -> [String] -> [String]\nbuscaCrucigramaR letra pos lon [] = []\nbuscaCrucigramaR letra pos lon (p:ps) \n    | length p == lon && 0 <= pos &#038;&#038; pos < length p &#038;&#038; p !! pos == letra \n        = p : buscaCrucigramaR letra pos lon ps\n    | otherwise \n        = buscaCrucigramaR letra pos lon ps\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.3. Comprobar con QuickCheck que ambas definiciones son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_buscaCrucigrama :: Char -> Int -> Int -> [String] -> Bool\nprop_buscaCrucigrama letra pos lon ps =\n    buscaCrucigrama letra pos lon ps == buscaCrucigramaR letra pos lon ps\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_buscaCrucigrama\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    posiciones :: String -> Char -> [Int]\n-- tal que (posiciones xs y) es la lista de la posiciones del car\u00e1cter y\n-- en la cadena xs. Por ejemplo,\n--    posiciones \"Salamamca\" 'a'  ==  [1,3,5,8]\n-- ---------------------------------------------------------------------\n\nposiciones :: String -> Char -> [Int]\nposiciones xs y = [n | (x,n) <- zip xs [0..], x == y]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    posicionesR :: String -> Char -> [Int]\n-- tal que (posicionesR xs y) es la lista de la posiciones del\n-- car\u00e1cter y en la cadena xs. Por ejemplo,\n--    posicionesR \"Salamamca\" 'a'  ==  [1,3,5,8]\n-- ---------------------------------------------------------------------\n\nposicionesR :: String -> Char -> [Int]\nposicionesR xs y = posicionesAux xs y 0\n    where\n      posicionesAux [] y n = []\n      posicionesAux (x:xs) y n | x == y    = n : posicionesAux xs y (n+1)\n                               | otherwise = posicionesAux xs y (n+1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.3. Comprobar con QuickCheck que ambas definiciones son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_posiciones :: String -> Char -> Bool\nprop_posiciones xs y = \n    posiciones xs y == posicionesR xs y\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_posiciones\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.1. Definir, por recursi\u00f3n, la funci\u00f3n\n--    contieneR :: String -> String -> Bool\n-- tal que (contieneR xs ys) se verifica si ys es una subcadena de\n-- xs. Por ejemplo, \n--    contieneR \"escasamente\" \"casa\"   ==  True\n--    contieneR \"escasamente\" \"cante\"  ==  False\n--    contieneR \"\" \"\"                  ==  True\n-- Nota: Se puede usar la predefinida (isPrefixOf ys xs) que se verifica\n-- si ys es un prefijo de xs.\n-- ---------------------------------------------------------------------\n\ncontieneR :: String -> String -> Bool\ncontieneR _ []  = True       \ncontieneR [] ys = False\ncontieneR xs ys = isPrefixOf ys xs || contieneR (tail xs) ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.2. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    contiene :: String -> String -> Bool\n-- tal que (contiene xs ys) se verifica si ys es una subcadena de\n-- xs. Por ejemplo, \n--    contiene \"escasamente\" \"casa\"      ==  True\n--    contiene \"escasamente\" \"cante\"     ==  False\n--    contiene \"casado y casada\" \"casa\"  ==  True\n--    contiene \"\" \"\"                     ==  True\n-- Nota: Se puede usar la predefinida (isPrefixOf ys xs) que se verifica\n-- si ys es un prefijo de xs.\n-- ---------------------------------------------------------------------\n\ncontiene :: String -> String -> Bool\ncontiene xs ys = \n    or [isPrefixOf ys zs | zs <- sufijos xs]\n\n-- (sufijos xs) es la lista de sufijos de xs. Por ejemplo,\n--    sufijos \"abc\"  ==  [\"abc\",\"bc\",\"c\",\"\"]\nsufijos :: String -> [String]\nsufijos xs = [drop i xs | i <- [0..length xs]]\n\n-- Notas: \n-- 1. La funci\u00f3n sufijos es equivalente a la predefinida tails.\n-- 2. contiene se puede definir usando la predefinida isInfixOf\n\ncontiene2 :: String -> String -> Bool\ncontiene2 xs ys = isInfixOf ys xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.3. Comprobar con QuickCheck que ambas definiciones son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_contiene :: String -> String -> Bool\nprop_contiene xs ys = \n    contieneR xs ys == contiene xs ys\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_contiene\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo anterior se encuentra tambi\u00e9n en <a href=\"http:\/\/bit.ly\/20gyspc\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones de los ejercicios de la 6\u00aa relaci\u00f3n que trata de funciones sobre cadenas. Los ejercicios, y sus soluciones, 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\/5138"}],"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=5138"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5138\/revisions"}],"predecessor-version":[{"id":5139,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5138\/revisions\/5139"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}