{"id":5349,"date":"2016-03-04T19:26:09","date_gmt":"2016-03-04T18:26:09","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5349"},"modified":"2016-03-05T09:31:33","modified_gmt":"2016-03-05T08:31:33","slug":"i1m2015-ejercicios-con-el-tipo-abstracto-de-dato-de-las-colas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-ejercicios-con-el-tipo-abstracto-de-dato-de-las-colas\/","title":{"rendered":"I1M2015: Ejercicios con el tipo abstracto de dato de las colas"},"content":{"rendered":"

En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han comentado las soluciones de los ejercicios de la relaci\u00f3n 24 sobre el tipo de datos abstracto de las colas.<\/p>\n

Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.
\n<\/p>\n

\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n de ejercicios es definir funciones sobre \n-- el TAD de las colas, utilizando las implementaciones estudiadas en el \n-- tema 15 transparencias se encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/temas\/tema-15.html\n-- \n-- Para realizar los ejercicios hay que instalar la librer\u00eda I1M que\n-- contiene la implementaci\u00f3n de TAD de las pilas. Los pasos para\n-- instalarla son los siguientes:\n-- + Descargar el paquete I1M desde http:\/\/bit.ly\/1pbnDqm\n-- + Descomprimirlo (y se crea el directorio I1M-master.zip).\n-- + Cambiar al directorio I1M-master.\n-- + Ejecutar cabal install I1M.cabal\n-- \n-- Otra forma es descargar las implementaciones de las implementaciones\n-- de las colas:\n-- + ColaConListas.hs    que est\u00e1 en http:\/\/bit.ly\/21z3wQL\n-- + ColaConDosListas.hs que est\u00e1 en http:\/\/bit.ly\/21z3AQp\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\nimport Data.List\nimport Test.QuickCheck\n\n-- Hay que elegir una implementaci\u00f3n del TAD colas:\nimport ColaConListas\n-- import ColaConDosListas\n-- import I1M.Cola\n    \n-- ---------------------------------------------------------------------\n-- Nota. A lo largo de la relaci\u00f3n de ejercicios usaremos los siguientes\n-- ejemplos de colas:\nc1, c2, c3, c4, c5, c6 :: Cola Int\nc1 = foldr inserta vacia [1..20]\nc2 = foldr inserta vacia [2,5..18]\nc3 = foldr inserta vacia [3..10]\nc4 = foldr inserta vacia [4,-1,7,3,8,10,0,3,3,4]\nc5 = foldr inserta vacia [15..20]\nc6 = foldr inserta vacia (reverse [1..20])\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1: Definir la funci\u00f3n\n--    ultimoCola :: Cola a -> a\n-- tal que (ultimoCola c) es el \u00faltimo elemento de la cola c. Por\n-- ejemplo:\n--    ultimoCola c4 == 4\n--    ultimoCola c5 == 15\n-- ---------------------------------------------------------------------\n\nultimoCola :: Cola a -> a\nultimoCola c\n    | esVacia c  = error \"cola vacia\"\n    | esVacia rc = pc\n    | otherwise  = ultimoCola rc\n    where pc = primero c\n          rc = resto c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2: Definir la funci\u00f3n\n--    longitudCola :: Cola a -> Int\n-- tal que (longitudCola c) es el n\u00famero de elementos de la cola c. Por\n-- ejemplo, \n--    longitudCola c2 == 6\n-- ---------------------------------------------------------------------\n\nlongitudCola :: Cola a -> Int\nlongitudCola c \n    | esVacia c = 0\n    | otherwise = 1 + longitudCola rc\n    where rc = resto c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3: Definir la funci\u00f3n \n--    todosVerifican :: (a -> Bool) -> Cola a -> Bool\n-- tal que (todosVerifican p c) se verifica si todos los elementos de la\n-- cola c cumplen la propiedad p. Por ejemplo,\n--    todosVerifican (>0) c1 == True\n--    todosVerifican (>0) c4 == False\n-- ---------------------------------------------------------------------\n\ntodosVerifican :: (a -> Bool) -> Cola a -> Bool\ntodosVerifican p c\n    | esVacia c = True\n    | otherwise = p pc && todosVerifican p rc\n    where pc = primero c\n          rc = resto c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4: Definir la funci\u00f3n\n--    algunoVerifica :: (a -> Bool) -> Cola a -> Bool\n-- tal que (algunoVerifica p c) se verifica si alg\u00fan elemento de la cola\n-- c cumple la propiedad p. Por ejemplo,\n--    algunoVerifica (<0) c1 == False\n--    algunoVerifica (<0) c4 == True\n-- ---------------------------------------------------------------------\n\nalgunoVerifica :: (a -> Bool) -> Cola a -> Bool\nalgunoVerifica p c\n    | esVacia c = False\n    | otherwise = p pc || algunoVerifica p rc\n    where pc = primero c\n          rc = resto c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5: Definir la funci\u00f3n\n--    ponAlaCola :: Cola a -> Cola a -> Cola a\n-- tal que (ponAlaCola c1 c2) es la cola que resulta de poner los\n-- elementos de c2 a la cola de c1. Por ejemplo,\n--    ponAlaCola c2 c3 == C [17,14,11,8,5,2,10,9,8,7,6,5,4,3]\n-- ---------------------------------------------------------------------\n\nponAlaCola :: Cola a -> Cola a -> Cola a\nponAlaCola c1 c2 \n    | esVacia c2 = c1\n    | otherwise  = ponAlaCola (inserta pc2 c1) rq2 \n    where pc2 = primero c2\n          rq2 = resto c2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6: Definir la funci\u00f3n\n--    mezclaColas :: Cola a -> Cola a -> Cola a\n-- tal que (mezclaColas c1 c2) es la cola formada por los elementos de\n-- c1 y c2 colocados en una cola, de forma alternativa, empezando por\n-- los elementos de c1. Por ejemplo,\n--    mezclaColas c2 c4 == C [17,4,14,3,11,3,8,0,5,10,2,8,3,7,-1,4]\n-- ---------------------------------------------------------------------\n\nmezclaColas :: Cola a -> Cola a -> Cola a\nmezclaColas c1 c2 = aux c1 c2 vacia\n    where aux c1 c2 c\n              | esVacia c1 = ponAlaCola c c2 \n              | esVacia c2 = ponAlaCola c c1\n              | otherwise = aux rc1 rc2 (inserta pc2 (inserta pc1 c))\n              where pc1 = primero c1\n                    rc1 = resto c1\n                    pc2 = primero c2\n                    rc2 = resto c2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7: Definir la funci\u00f3n\n--    agrupaColas :: [Cola a] -> Cola a\n-- tal que (agrupaColas [c1,c2,c3,...,cn]) es la cola formada mezclando\n-- las colas de la lista como sigue: mezcla c1 con c2, el resultado con\n-- c3, el resultado con c4, y as\u00ed sucesivamente. Por ejemplo,\n--    ghci> agrupaColas [c3,c3,c4]\n--    C [10,4,10,3,9,3,9,0,8,10,8,8,7,3,7,7,6,-1,6,4,5,5,4,4,3,3]\n-- ---------------------------------------------------------------------\n\nagrupaColas :: [Cola a] -> Cola a\nagrupaColas []            = vacia\nagrupaColas [c]           = c\nagrupaColas (c1:c2:colas) = agrupaColas (mezclaColas c1 c2 : colas)\n\n-- 2\u00aa soluci\u00f3n\nagrupaColas2 :: [Cola a] -> Cola a\nagrupaColas2 = foldl mezclaColas vacia\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8: Definir la funci\u00f3n\n--    perteneceCola :: Eq a => a -> Cola a -> Bool\n-- tal que (perteneceCola x c) se verifica si x es un elemento de la\n-- cola c. Por ejemplo, \n--    perteneceCola 7 c1  == True\n--    perteneceCola 70 c1 == False\n-- ---------------------------------------------------------------------\n\nperteneceCola :: Eq a => a -> Cola a -> Bool\nperteneceCola x c \n    | esVacia c  = False\n    | otherwise  = pc == x || perteneceCola x rc\n    where pc = primero c\n          rc = resto c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9: Definir la funci\u00f3n\n--    contenidaCola :: Eq a => Cola a -> Cola a -> Bool\n-- tal que (contenidaCola c1 c2) se verifica si todos los elementos de\n-- c1 son elementos de c2. Por ejemplo, \n--    contenidaCola c2 c1 == True\n--    contenidaCola c1 c2 == False\n-- ---------------------------------------------------------------------\n\ncontenidaCola :: Eq a => Cola a -> Cola a -> Bool\ncontenidaCola c1 c2 \n    | esVacia c1 = True\n    | esVacia c2 = False\n    | otherwise  = perteneceCola pc1 c2 && contenidaCola rc1 c2 \n    where pc1 = primero c1\n          rc1 = resto c1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10: Definir la funci\u00f3n\n--    prefijoCola :: Eq a => Cola a -> Cola a -> Bool\n-- tal que (prefijoCola c1 c2) se verifica si la cola c1 es un prefijo\n-- de la cola c2. Por ejemplo, \n--    prefijoCola c3 c2 == False\n--    prefijoCola c5 c1 == True\n-- ---------------------------------------------------------------------\n\nprefijoCola :: Eq a => Cola a -> Cola a -> Bool\nprefijoCola c1 c2 \n    | esVacia c1 = True\n    | esVacia c2 = False\n    | otherwise  = pc1 == pc2 && prefijoCola rc1 rc2\n    where pc1 = primero c1\n          rc1 = resto c1\n          pc2 = primero c2\n          rc2 = resto c2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11: Definir la funci\u00f3n\n--    subCola :: Eq a => Cola a -> Cola a -> Bool\n-- tal que (subCola c1 c2) se verifica si c1 es una subcola de c2. Por\n-- ejemplo,  \n--    subCola c2 c1 == False\n--    subCola c3 c1 == True\n-- ---------------------------------------------------------------------\n\nsubCola :: Eq a => Cola a -> Cola a -> Bool\nsubCola c1 c2 \n    | esVacia c1 = True\n    | esVacia c2 = False\n    | pc1 == pc2 = prefijoCola rc1 rc2 || subCola c1 rc2\n    | otherwise  = subCola c1 rc2\n    where pc1 = primero c1\n          rc1 = resto c1\n          pc2 = primero c2\n          rc2 = resto c2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12: Definir la funci\u00f3n\n--    ordenadaCola :: Ord a => Cola a -> Bool\n-- tal que (ordenadaCola c) se verifica si los elementos de la cola c\n-- est\u00e1n ordenados en orden creciente. Por ejemplo,\n--    ordenadaCola c6 == True\n--    ordenadaCola c4 == False\n-- ---------------------------------------------------------------------\n\nordenadaCola :: Ord a => Cola a -> Bool\nordenadaCola c \n    | esVacia c = True\n    | esVacia rc = True\n    | otherwise = pc <= prc && ordenadaCola rc\n    where pc  = primero c\n          rc  = resto c\n          prc = primero rc\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13.1: Definir una funci\u00f3n\n--    lista2Cola :: [a] -> Cola a\n-- tal que (lista2Cola xs) es una cola formada por los elementos de xs.\n-- Por ejemplo,\n--    lista2Cola [1..6] == C [1,2,3,4,5,6]\n-- ---------------------------------------------------------------------\n\nlista2Cola :: [a] -> Cola a\nlista2Cola xs = foldr inserta vacia (reverse xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13.2: Definir una funci\u00f3n\n--    cola2Lista :: Cola a -> [a]\n-- tal que (cola2Lista c) es la lista formada por los elementos de p.\n-- Por ejemplo,\n--    cola2Lista c2 == [17,14,11,8,5,2]\n-- ---------------------------------------------------------------------\n\ncola2Lista :: Cola a -> [a]\ncola2Lista c\n    | esVacia c = []\n    | otherwise = pc : cola2Lista rc\n    where pc = primero c\n          rc = resto c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13.3. Comprobar con QuickCheck que la funci\u00f3n cola2Lista es\n-- la inversa de  lista2Cola, y rec\u00edprocamente.\n-- ---------------------------------------------------------------------\n\nprop_cola2Lista :: Cola Int -> Bool\nprop_cola2Lista c =\n    lista2Cola (cola2Lista c) == c\n\n-- ghci> quickCheck prop_cola2Lista\n-- +++ OK, passed 100 tests.\n\nprop_lista2Cola :: [Int] -> Bool\nprop_lista2Cola xs =\n    cola2Lista (lista2Cola xs) == xs\n\n-- ghci> quickCheck prop_lista2Cola\n-- +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14: Definir la funci\u00f3n \n--    maxCola :: Ord a => Cola a -> a\n-- tal que (maxCola c) es el mayor de los elementos de la cola c. Por\n-- ejemplo, \n--    maxCola c4 == 10\n-- ---------------------------------------------------------------------\n\nmaxCola :: Ord a => Cola a -> a\nmaxCola c \n    | esVacia c = error \"cola vacia\"\n    | esVacia rc = pc\n    | otherwise = max pc (maxCola rc)\n    where pc = primero c\n          rc = resto c\n\nprop_maxCola c =\n    not (esVacia c) ==>\n        maxCola c == maximum (cola2Lista c)\n\n-- ghci> quickCheck prop_maxCola\n-- +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Generador de colas                                          --\n-- ---------------------------------------------------------------------\n\n-- genCola es un generador de colas de enteros. Por ejemplo,\n--    ghci> sample genCola\n--    C ([],[])\n--    C ([],[])\n--    C ([],[])\n--    C ([],[])\n--    C ([7,8,4,3,7],[5,3,3])\n--    C ([],[])\n--    C ([1],[13])\n--    C ([18,28],[12,21,28,28,3,18,14])\n--    C ([47],[64,45,7])\n--    C ([8],[])\n--    C ([42,112,178,175,107],[])\ngenCola :: (Num a, Arbitrary a) => Gen (Cola a)\ngenCola = frequency [(1, return vacia),\n                     (30, do n <- choose (10,100)\n                             xs <- vectorOf n arbitrary\n                             return (creaCola xs))]\n          where creaCola = foldr inserta vacia\n\n-- El tipo cola es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Cola a) where\n    arbitrary = genCola\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han comentado las soluciones de los ejercicios de la relaci\u00f3n 24 sobre el tipo de datos abstracto de las colas. 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":[244,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\/5349"}],"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=5349"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5349\/revisions"}],"predecessor-version":[{"id":5350,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5349\/revisions\/5350"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5349"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5349"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5349"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}