{"id":1741,"date":"2011-12-03T16:26:01","date_gmt":"2011-12-03T16:26:01","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1741"},"modified":"2013-03-08T05:48:58","modified_gmt":"2013-03-08T05:48:58","slug":"segmentos-de-una-lista-que-verifican-una-propiedad","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/segmentos-de-una-lista-que-verifican-una-propiedad\/","title":{"rendered":"Segmentos de una lista que verifican una propiedad"},"content":{"rendered":"<p>He a\u00f1adido a <a href=\"https:\/\/www.glc.us.es\/~jalonso\/LogicaMente\/index.php5\/Segmentos_de_una_lista_que_verifican_una_propiedad\">L\u00f3gicaMente<\/a> la siguiente relaci\u00f3n de ejercicios que ilustra el uso de las funciones de orden superior en Haskell y la comprobaci\u00f3n de sus propiedades con QuickCheck.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck \r\nimport Text.Show.Functions\r\nimport Data.List \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    esPrefijo :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (esPrefijo xs ys) se verifica si xs es un prefijo de ys; es\r\n-- decir una lista de elementos consecutivos de ys empezando por su\r\n-- primer elemento. Por ejemplo, \r\n--    esPrefijo [2,5] [2,5,3]  ==  True\r\n--    esPrefijo [2,5] [2,3,5]  ==  False\r\n--    esPrefijo [2,5] [3,2,5]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesPrefijo :: Eq a => [a] -> [a] -> Bool\r\nesPrefijo [] _ = True\r\nesPrefijo (x:xs) (y:ys) = x == y && esPrefijo xs ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    esSegmento :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (esSegmento xs ys) se verifica si xs es un segmento de ys; es\r\n-- decir, una lista de elementos consecutivos de ys. Por ejemplo,  \r\n--    esSegmento [2,5] [2,5,3]  ==  True\r\n--    esSegmento [2,5] [2,3,5]  ==  False\r\n--    esSegmento [2,5] [3,2,5]  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nesSegmento :: Eq a => [a] -> [a] -> Bool\r\nesSegmento [] _  = True \r\nesSegmento _ []  = False\r\nesSegmento xs (y:ys) = \r\n    esPrefijo xs (y:ys) || esSegmento xs ys \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    segmentos :: (a -> Bool) -> [a] -> [[a]]\r\n-- tal que (segmentos p xs) es la lista de los segmentos de xs que\r\n-- verifican la propiedad p. Por ejemplo,\r\n--   segmentos (>3) [4,2,0,7,0,6,8,9,5,4] == [[4],[7],[6,8,9,5,4]]\r\n--   segmentos even [4,2,0,7,0,6,8,9,5,4] == [[4,2,0],[0,6,8],[4]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsegmentos :: (a -> Bool) -> [a] -> [[a]]\r\nsegmentos p [] = []\r\nsegmentos p xs = \r\n    takeWhile p xs : segmentos p (dropWhile (not . p) (dropWhile p xs))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Comprobar con QuickCheck que para toda propiedad p y\r\n-- toda lista xs, los elementos de (segmentos p xs) son segmentos de\r\n-- xs. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_segmentosDaSegmentos :: (Int -> Bool) -> [Int] -> Bool \r\nprop_segmentosDaSegmentos p xs = \r\n    and [esSegmento ys xs | ys <- segmentos p xs]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_segmentosDaSegmentos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Comprobar con QuickCheck que para toda propiedad p y\r\n-- toda lista xs, los elementos de los elementos de (segmentos p xs)\r\n-- cumplen la propiedad p.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_segmentosCumplen1 :: (Int -> Bool) -> [Int] -> Bool \r\nprop_segmentosCumplen1 p xs = \r\n    and [p x | x <- concat (segmentos p xs)]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_segmentosCumplen1\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Comprobar con QuickCheck que para toda propiedad p y\r\n-- toda lista xs, los elementos de xs que no pertenece a ninguno de los\r\n-- elementos de (segmentos p xs) no cumplen la propiedad p.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_segmentosCumplen2 :: (Int -> Bool) -> [Int] -> Bool \r\nprop_segmentosCumplen2 p xs = \r\n    and [not (p x) | x <- xs \\\\ concat (segmentos p xs)]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_segmentosCumplen2\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Comprobar con QuickCheck que para toda propiedad p y\r\n-- toda lista xs, los suma de las longitudes de los elementos de \r\n-- (segmentos p xs) es el n\u00famero de elementos de xs que cumplen p.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_segmentosLongitud1 :: (Int -> Bool) -> [Int] -> Bool \r\nprop_segmentosLongitud1 p xs = \r\n    sum [length ys | ys <- segmentos p xs] == length (filter p xs) \r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_segmentosLongitud1\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Comprobar con QuickCheck que para toda propiedad p y\r\n-- toda lista xs, el n\u00famero de elementos de xs que no pertenecen a\r\n-- ninguno de los elementos de (segmentos p xs) es el n\u00famero de los\r\n-- elementos de xs que no cumplen la propiedad p.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_segmentosLongitud2 :: (Int -> Bool) -> [Int] -> Bool \r\nprop_segmentosLongitud2 p xs = \r\n    length (xs \\\\ concat (segmentos p xs)) == \r\n    length (filter (not . p) xs) \r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_segmentosLongitud2\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>He a\u00f1adido a L\u00f3gicaMente la siguiente relaci\u00f3n de ejercicios que ilustra el uso de las funciones de orden superior en Haskell y la comprobaci\u00f3n de sus propiedades con QuickCheck.<\/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":[27,270,175,126],"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\/1741"}],"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=1741"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1741\/revisions"}],"predecessor-version":[{"id":2894,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1741\/revisions\/2894"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1741"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1741"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1741"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}