{"id":3856,"date":"2013-11-26T16:07:37","date_gmt":"2013-11-26T15:07:37","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3856"},"modified":"2013-11-27T06:09:23","modified_gmt":"2013-11-27T05:09:23","slug":"i1m2013-verificacion-de-la-ordenacion-por-mezcla-con-quickcheck","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-verificacion-de-la-ordenacion-por-mezcla-con-quickcheck\/","title":{"rendered":"I1M2013: Verificaci\u00f3n de la ordenaci\u00f3n por mezcla con QuickCheck"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha estudiado la verificaci\u00f3n de propiedades con QuickCheck y, como aplicaci\u00f3n, se ha estudiado la verificaci\u00f3n de la ordenaci\u00f3n por mezcla siguiendo los ejercicios de la relaci\u00f3n 9.<\/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-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El objetivo de esta relaci\u00f3n es definir la ordenaci\u00f3n por mezclas y\r\n-- comprobar su correcci\u00f3n con QuickCheck.\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    mezcla :: Ord a => [a] -> [a] -> [a] \r\n-- tal que (mezcla xs ys) es la lista obtenida mezclando las listas\r\n-- ordenadas xs e ys. Por ejemplo,  \r\n--    mezcla [2,5,6] [1,3,4]  ==  [1,2,3,4,5,6]\r\n-- ---------------------------------------------------------------------\r\n\r\nmezcla :: Ord a => [a] -> [a] -> [a] \r\nmezcla []     ys                 = ys\r\nmezcla xs     []                 = xs\r\nmezcla (x:xs) (y:ys) | x <= y    = x : mezcla xs (y:ys)\r\n                     | otherwise = y : mezcla (x:xs) ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n \r\n--    mitades :: [a] -> ([a],[a]) \r\n-- tal que (mitades xs) es el par formado por las dos mitades en que se\r\n-- divide xs tales que sus longitudes difieren como m\u00e1ximo en uno. Por\r\n-- ejemplo, \r\n--    mitades [2,3,5,7,9]  ==  ([2,3],[5,7,9])\r\n-- ---------------------------------------------------------------------\r\n\r\nmitades :: [a] -> ([a],[a]) \r\nmitades xs = splitAt (length xs `div` 2) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir por recursi\u00f3n la funci\u00f3n \r\n--    ordMezcla :: Ord a => [a] -> [a]\r\n-- tal que (ordMezcla xs) es la lista obtenida ordenado xs por mezcla\r\n-- (es decir, considerando que la lista vac\u00eda y las listas unitarias\r\n-- est\u00e1n ordenadas y cualquier otra lista se ordena mezclando las dos\r\n-- listas que resultan de ordenar sus dos mitades por separado). Por\r\n-- ejemplo, \r\n--    ordMezcla [5,2,3,1,7,2,5]  ==  [1,2,2,3,5,5,7]\r\n-- ---------------------------------------------------------------------\r\n\r\nordMezcla :: Ord a => [a] -> [a]\r\nordMezcla []  = []\r\nordMezcla [x] = [x]\r\nordMezcla xs  = mezcla (ordMezcla ys) (ordMezcla zs)\r\n                where (ys,zs) = mitades xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir por recursi\u00f3n la funci\u00f3n\r\n--    ordenada :: Ord a => [a] -> Bool\r\n-- tal que (ordenada xs) se verifica si xs es una lista ordenada. Por\r\n-- ejemplo, \r\n--    ordenada [2,3,5]  ==  True\r\n--    ordenada [2,5,3]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nordenada :: Ord a => [a] -> Bool\r\nordenada []       = True\r\nordenada [_]      = True\r\nordenada (x:y:xs) = x <= y &#038;&#038; ordenada (y:xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Comprobar con QuickCheck que la ordenaci\u00f3n por mezcla\r\n-- de una lista es una lista ordenada.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_ordMezcla_ordenada :: [Int] -> Bool\r\nprop_ordMezcla_ordenada xs = ordenada (ordMezcla xs)\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_ordMezcla_ordenada\r\n--    +++ OK, passed 100 tests.\r\n    \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir por recursi\u00f3n la funci\u00f3n\r\n--    borra :: Eq a => a -> [a] -> [a]\r\n-- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de\r\n-- x en la lista xs. Por ejemplo, \r\n--    borra 1 [1,2,1]  ==  [2,1]\r\n--    borra 3 [1,2,1]  ==  [1,2,1]\r\n-- ---------------------------------------------------------------------\r\n\r\nborra :: Eq a => a -> [a] -> [a]\r\nborra x []                 = []\r\nborra x (y:ys) | x == y    = ys\r\n               | otherwise = y : borra x ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir por recursi\u00f3n la funci\u00f3n \r\n--    esPermutacion :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (esPermutacion xs ys) se verifica si xs es una permutaci\u00f3n de\r\n-- ys. Por ejemplo, \r\n--    esPermutacion [1,2,1] [2,1,1]  ==  True\r\n--    esPermutacion [1,2,1] [1,2,2]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesPermutacion :: Eq a => [a] -> [a] -> Bool\r\nesPermutacion []     []     = True\r\nesPermutacion []     (y:ys) = False\r\nesPermutacion (x:xs) ys     = elem x ys && esPermutacion xs (borra x ys)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Comprobar con QuickCheck que la ordenaci\u00f3n por mezcla\r\n-- de una lista es una permutaci\u00f3n de la lista.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_ordMezcla_pemutacion :: [Int] -> Bool\r\nprop_ordMezcla_pemutacion xs = esPermutacion (ordMezcla xs) xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_ordMezcla_pemutacion\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 se ha estudiado la verificaci\u00f3n de propiedades con QuickCheck y, como aplicaci\u00f3n, se ha estudiado la verificaci\u00f3n de la ordenaci\u00f3n por mezcla siguiendo los ejercicios de la relaci\u00f3n 9. Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[222],"tags":[270,300,228],"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\/3856"}],"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=3856"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3856\/revisions"}],"predecessor-version":[{"id":3857,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3856\/revisions\/3857"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3856"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3856"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3856"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}