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