{"id":5347,"date":"2016-03-04T19:23:03","date_gmt":"2016-03-04T18:23:03","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5347"},"modified":"2016-03-05T09:24:06","modified_gmt":"2016-03-05T08:24:06","slug":"i1m2015-ejercicios-con-el-tipo-abstracto-de-dato-de-las-pilas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-ejercicios-con-el-tipo-abstracto-de-dato-de-las-pilas\/","title":{"rendered":"I1M2015: Ejercicios con el tipo abstracto de dato de las pilas"},"content":{"rendered":"<p>En la primera parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">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 pilas.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n de ejercicios es definir funciones sobre \n-- el TAD de las pilas, utilizando las implementaciones estudiadas en el \n-- tema 14 cuyas transparencias se encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/temas\/tema-14.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 pilas:\n-- + PilaConTipoDeDatoAlgebraico.hs que est\u00e1 en http:\/\/bit.ly\/21z3g49\n-- + PilaConListas.hs               que est\u00e1 en http:\/\/bit.ly\/21z3oAD\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 pilas.\nimport PilaConTipoDeDatoAlgebraico\n-- import PilaConListas\n-- import I1M.Pila\n\n-- ---------------------------------------------------------------------\n-- Ejemplos\n-- ---------------------------------------------------------------------\n\n-- A lo largo de esta relaci\u00f3n de ejercicios usaremos los siguientes\n-- ejemplos de pila\np1, p2, p3, p4, p5 :: Pila Int\np1 = foldr apila vacia [1..20]\np2 = foldr apila vacia [2,5..18]\np3 = foldr apila vacia [3..10]\np4 = foldr apila vacia [4,-1,7,3,8,10,0,3,3,4]\np5 = foldr apila vacia [1..5]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1: Definir la funci\u00f3n\n--    filtraPila :: (a -> Bool) -> Pila a -> Pila a\n-- tal que (filtraPila p q) es la pila obtenida con los elementos de\n-- pila q que verifican el predicado p, en el mismo orden. Por ejemplo,\n--    ghci> p1\n--    1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|-\n--    ghci> filtraPila even p1\n--    2|4|6|8|10|12|14|16|18|20|-\n-- ---------------------------------------------------------------------\n\nfiltraPila :: (a -> Bool) -> Pila a -> Pila a\nfiltraPila p q\n    | esVacia q = vacia\n    | p cq      = apila cq (filtraPila p dq)\n    | otherwise = filtraPila p dq\n    where cq = cima q\n          dq = desapila q\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2: Definir la funci\u00f3n\n--    mapPila :: (a -> a) -> Pila a -> Pila a\n-- tal que (mapPila f p) es la pila formada con las im\u00e1genes por f de\n-- los elementos de pila p, en el mismo orden. Por ejemplo,\n--    ghci> mapPila (+7) p1\n--    8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|-\n-- ---------------------------------------------------------------------\n\nmapPila :: (a -> a) -> Pila a -> Pila a\nmapPila f p\n    | esVacia p = p\n    | otherwise = apila (f cp) (mapPila f dp)\n    where cp = cima p\n          dp = desapila p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3: Definir la funci\u00f3n\n--    pertenecePila :: Eq a => a -> Pila a -> Bool\n-- tal que (pertenecePila y p) se verifica si y es un elemento de la\n-- pila p. Por ejemplo,\n--    pertenecePila 7 p1  == True\n--    pertenecePila 70 p1 == False\n-- ---------------------------------------------------------------------\n\npertenecePila :: Eq a => a -> Pila a -> Bool\npertenecePila x p \n    | esVacia p  = False\n    | otherwise  = x == cp || pertenecePila x dp\n    where cp = cima p\n          dp = desapila p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4: Definir la funci\u00f3n\n--    contenidaPila :: Eq a => Pila a -> Pila a -> Bool\n-- tal que (contenidaPila p1 p2) se verifica si todos los elementos de\n-- de la pila p1 son elementos de la pila p2. Por ejemplo,\n--    contenidaPila p2 p1  == True\n--    contenidaPila p1 p2  == False\n-- ---------------------------------------------------------------------\n\ncontenidaPila :: Eq a => Pila a -> Pila a -> Bool\ncontenidaPila p1 p2 \n    | esVacia p1 = True\n    | otherwise  = pertenecePila cp1 p2 && contenidaPila dp1 p2 \n    where cp1 = cima p1\n          dp1 = desapila p1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4: Definir la funci\u00f3n\n--    prefijoPila :: Eq a => Pila a -> Pila a -> Bool\n-- tal que (prefijoPila p1 p2) se verifica si la pila p1 es justamente\n-- un prefijo de la pila p2. Por ejemplo,\n--    prefijoPila p3 p2 == False\n--    prefijoPila p5 p1 == True\n-- ---------------------------------------------------------------------\n\nprefijoPila :: Eq a => Pila a -> Pila a -> Bool\nprefijoPila p1 p2 \n    | esVacia p1 = True\n    | esVacia p2 = False\n    | otherwise  = cp1 == cp2 && prefijoPila dp1 dp2\n    where cp1 = cima p1\n          dp1 = desapila p1\n          cp2 = cima p2\n          dp2 = desapila p2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    subPila :: Eq a => Pila a -> Pila a -> Bool\n-- tal que (subPila p1 p2) se verifica si p1 es una subpila de p2. Por\n-- ejemplo,\n--    subPila p2 p1 == False\n--    subPila p3 p1 == True\n-- ---------------------------------------------------------------------\n\nsubPila :: Eq a => Pila a -> Pila a -> Bool\nsubPila p1 p2\n    | esVacia p1 = True\n    | esVacia p2 = False\n    | cp1 == cp2 = prefijoPila dp1 dp2 || subPila p1 dp2\n    | otherwise  = subPila p1 dp2\n    where cp1 = cima p1\n          dp1 = desapila p1\n          cp2 = cima p2\n          dp2 = desapila p2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    ordenadaPila :: Ord a => Pila a -> Bool\n-- tal que (ordenadaPila p) se verifica si los elementos de la pila p\n-- est\u00e1n ordenados en orden creciente. Por ejemplo,\n--    ordenadaPila p1 == True\n--    ordenadaPila p4 == False\n-- ---------------------------------------------------------------------\n\nordenadaPila :: Ord a => Pila a -> Bool\nordenadaPila p \n    | esVacia p  = True\n    | esVacia dp = True\n    | otherwise  = cp <= cdp &#038;&#038; ordenadaPila dp\n    where cp  = cima p\n          dp  = desapila p\n          cdp = cima dp\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Definir la funci\u00f3n\n--    lista2Pila :: [a] -> Pila a\n-- tal que (lista2Pila xs) es la pila formada por los elementos de\n-- xs. Por ejemplo,\n--    lista2Pila [1..6] == 1|2|3|4|5|6|-\n-- ---------------------------------------------------------------------\n\nlista2Pila :: [a] -> Pila a\nlista2Pila = foldr apila vacia\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Definir la funci\u00f3n\n--    pila2Lista :: Pila a -> [a]\n-- tal que (pila2Lista p) es la lista formada por los elementos de la\n-- lista p. Por ejemplo,\n--    pila2Lista p2 == [2,5,8,11,14,17]\n-- ---------------------------------------------------------------------\n\npila2Lista :: Pila a -> [a]\npila2Lista p\n    | esVacia p = []\n    | otherwise = cp : pila2Lista dp\n    where cp = cima p\n          dp = desapila p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.3. Comprobar con QuickCheck que la funci\u00f3n pila2Lista es\n-- la inversa de lista2Pila, y rec\u00edprocamente.\n-- ---------------------------------------------------------------------\n\nprop_pila2Lista p =\n    lista2Pila (pila2Lista p) == p\n\n-- ghci> quickCheck prop_pila2Lista\n-- +++ OK, passed 100 tests.\n\nprop_lista2Pila xs =\n    pila2Lista (lista2Pila xs) == xs\n\n-- ghci> quickCheck prop_lista2Pila\n-- +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.1. Definir la funci\u00f3n \n--    ordenaInserPila :: Ord a => Pila a -> Pila a\n-- tal que (ordenaInserPila p) es la pila obtenida ordenando por\n-- inserci\u00f3n los los elementos de la pila p. Por ejemplo,\n--    ghci> ordenaInserPila p4\n--    -1|0|3|3|3|4|4|7|8|10|-\n-- ---------------------------------------------------------------------\n\nordenaInserPila :: Ord a => Pila a -> Pila a\nordenaInserPila p\n    | esVacia p = p\n    | otherwise = insertaPila cp (ordenaInserPila dp)\n    where cp = cima p\n          dp = desapila p\n\ninsertaPila :: Ord a => a -> Pila a -> Pila a\ninsertaPila x p \n    | esVacia p = apila x p\n    | x < cp    = apila x p\n    | otherwise = apila cp (insertaPila x dp)\n    where cp = cima p\n          dp = desapila p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.2. Comprobar con QuickCheck que la pila \n--    (ordenaInserPila p) \n-- est\u00e1 ordenada correctamente.\n-- ---------------------------------------------------------------------\n\nprop_ordenaInserPila p =\n    pila2Lista (ordenaInserPila p) == sort (pila2Lista p)\n\n-- ghci> quickCheck prop_ordenaInserPila\n-- +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.1. Definir la funci\u00f3n\n--    nubPila :: Eq a => Pila a -> Pila a\n-- tal que (nubPila p) es la pila con los elementos de p sin repeticiones. \n-- Por ejemplo,\n--    ghci> p4\n--    4|-1|7|3|8|10|0|3|3|4|-\n--    ghci> nubPila p4\n--    -1|7|8|10|0|3|4|-\n-- ---------------------------------------------------------------------\n\nnubPila :: (Eq a) => Pila a -> Pila a\nnubPila p \n    | esVacia p           = vacia\n    | pertenecePila cp dp = nubPila dp\n    | otherwise           = apila cp (nubPila dp)\n    where cp = cima p\n          dp = desapila p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.2. Definir la propiedad siguiente: \"la composici\u00f3n de\n-- las funciones nub y pila2Lista coincide con la composici\u00f3n de las\n-- funciones pila2Lista y nubPila\", y comprobarla con QuickCheck.\n-- En caso de ser falsa, redefinir la funci\u00f3n nubPila para que se\n-- verifique la propiedad.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_nubPila p =\n    nub (pila2Lista p) == pila2Lista (nubPila p)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_nubPila\n--    *** Failed! Falsifiable (after 8 tests):  \n--    -7|-2|0|-5|-7|-\n--    ghci> let p = foldr apila vacia [-7,-2,0,-5,-7]\n--    ghci> p\n--    -7|-2|0|-5|-7|-\n--    ghci> pila2Lista p\n--    [-7,-2,0,-5,-7]\n--    ghci> nub (pila2Lista p)\n--    [-7,-2,0,-5]\n--    ghci> nubPila p\n--    -2|0|-5|-7|-\n--    ghci> pila2Lista (nubPila p)\n--    [-2,0,-5,-7]\n\n-- Falla porque nub quita el \u00faltimo de los elementos repetidos de la\n-- lista, mientras que nubPila quita el primero de ellos.\n\n-- La redefinimos\nnubPila' :: Eq a => Pila a -> Pila a\nnubPila' p \n    | esVacia p           = p\n    | pertenecePila cp dp = apila cp (nubPila' (eliminaPila cp dp))\n    | otherwise           = apila cp (nubPila' dp)\n    where cp = cima p\n          dp = desapila p\n\neliminaPila :: Eq a => a -> Pila a -> Pila a\neliminaPila x p \n    | esVacia p = p\n    | x == cp    = eliminaPila x dp\n    | otherwise = apila cp (eliminaPila x dp)\n    where cp = cima p\n          dp = desapila p\n\n-- La propiedad es\nprop_nubPila' p =\n    nub (pila2Lista p) == pila2Lista (nubPila' p)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_nubPila'\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10: Definir la funci\u00f3n \n--    maxPila :: Ord a => Pila a -> a\n-- tal que (maxPila p) sea el mayor de los elementos de la pila p. Por\n-- ejemplo, \n--    ghci> p4\n--    4|-1|7|3|8|10|0|3|3|4|-\n--    ghci> maxPila p4\n--    10\n-- ---------------------------------------------------------------------\n\nmaxPila :: Ord a => Pila a -> a\nmaxPila p \n    | esVacia p = error \"pila vacia\"\n    | esVacia dp = cp\n    | otherwise = max cp (maxPila dp)\n    where cp = cima p\n          dp = desapila p\n\n-- ---------------------------------------------------------------------\n-- Generador de pilas                                          --\n-- ---------------------------------------------------------------------\n\n-- genPila es un generador de pilas. Por ejemplo,\n--    ghci> sample genPila\n--    -\n--    0|0|-\n--    -\n--    -6|4|-3|3|0|-\n--    -\n--    9|5|-1|-3|0|-8|-5|-7|2|-\n--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-\n--    2|-14|-5|2|-\n--    5|9|-\n--    -1|-14|5|-\n--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-\ngenPila :: (Num a, Arbitrary a) => Gen (Pila a)\ngenPila = do xs <- listOf arbitrary\n             return (foldr apila vacia xs)\n  \n-- El tipo pila es una instancia del arbitrario. \ninstance (Arbitrary a, Num a) => Arbitrary (Pila a) where\n    arbitrary = genPila\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 se han comentado las soluciones de los ejercicios de la relaci\u00f3n 24 sobre el tipo de datos abstracto de las pilas. 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\/5347"}],"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=5347"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5347\/revisions"}],"predecessor-version":[{"id":5348,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5347\/revisions\/5348"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5347"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5347"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5347"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}