{"id":2437,"date":"2012-12-18T17:07:27","date_gmt":"2012-12-18T17:07:27","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2437"},"modified":"2013-03-08T05:47:36","modified_gmt":"2013-03-08T05:47:36","slug":"i1m2012-problemas-8-y-9-y-ejercicios-sobre-cadenas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-problemas-8-y-9-y-ejercicios-sobre-cadenas\/","title":{"rendered":"I1M2012: Problemas 8 y 9 y ejercicios sobre cadenas"},"content":{"rendered":"<p>En la primera parte de 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 problemas 8 (<a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-el-problema-de-las-numeros-bonitos-y-numeros-feos-en-haskell\">n\u00fameros bonitos y n\u00fameros feos<\/a>) y 9 (<a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-ceros-finales-del-factorial\/\">ceros finales del factorial<\/a>).<\/p>\n<p>En la segunda parte hemos comentado las soluciones de los ejercicios 4 y 6 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 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 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 primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones de los problemas 8 (n\u00fameros bonitos y n\u00fameros feos) y 9 (ceros finales del factorial). En la segunda parte hemos comentado las soluciones de los ejercicios 4 y 6 de la 12\u00aa relaci\u00f3n de&#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":[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\/2437"}],"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=2437"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2437\/revisions"}],"predecessor-version":[{"id":2718,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2437\/revisions\/2718"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2437"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}