{"id":840,"date":"2010-11-16T01:32:10","date_gmt":"2010-11-16T01:32:10","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=840"},"modified":"2013-03-08T05:50:08","modified_gmt":"2013-03-08T05:50:08","slug":"el-tipo-abstracto-de-datos-de-las-pilas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-las-pilas-en-haskell\/","title":{"rendered":"El tipo abstracto de datos de las pilas en Haskell"},"content":{"rendered":"<p>\nEn este art\u00edculo contin\u00fao la serie dedicada a los <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/tag\/tipo-abstracto-de-datos\/\">tipos de datos abstractos (TAD) en Haskell<\/a> presentando el TAD de las pilas.<\/p>\n<p>\nEn art\u00edculos anteriores present\u00e9 los TAD de los <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-los-polinomios-en-haskell\/\">polinomios<\/a> y el de los <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-los-conjuntos-en-haskell\/\">conjuntos<\/a>. En \u00e9ste voy a presentar el TAD de las pilas y sus implementaciones en Haskell. <\/p>\n<p>\nAl igual que hice en los anteriores TAD, usar\u00e9 m\u00f3dulos, funciones de escritura y QuickCheck para conseguir la abstracci\u00f3n, independencia y certificaci\u00f3n de los resultados de las implementaciones.<\/p>\n<p>\nEl contenido del resto del art\u00edculo es el siguiente: el TAD de las pilas, las implementaciones en Haskell mediante tipos algebraicos y mediante listas y la comprobaci\u00f3n con QuickCheck de sus propiedades.<br \/>\n<!--more--><\/p>\n<h3><i>Pila.hs<\/i>: El TAD de las pilas<\/h3>\n<pre lang=\"haskell\">\r\nmodule Pila (Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where\r\n\r\n-- El tipo de las pilas.\r\ndata Pila a = Undefined\r\n\r\n-- pilaVacia es la pila vac\u00eda. \r\npilaVacia :: Pila a\r\npilaVacia = undefined\r\n\r\n-- (esPilaVacia p) se verifica si p es la pila vac\u00eda.\r\nesPilaVacia :: Pila a -> Bool\r\nesPilaVacia = undefined\r\n\r\n-- (apilar x p) es la pila obtenida a\u00f1adi\u00e9ndole x encima de la pila\r\n-- p.\r\napilar :: a -> Pila a -> Pila a\r\napilar = undefined\r\n\r\n-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila\r\n-- p.\r\ndesapilar :: Pila a -> Pila a\r\ndesapilar = undefined\r\n\r\n-- (cima p) es la cima de la pila p.\r\ncima :: Pila a -> a\r\ncima = undefined\r\n<\/pre>\n<h3><i>PilaConTipoDeDatoAlgebraico.hs<\/i>: Implemetaci\u00f3n de las pilas mediante tipos algebraicos<\/h3>\n<pre lang=\"haskell\">\r\nmodule PilaConTipoDeDatoAlgebraico \r\n    (Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where\r\n\r\nimport qualified Pila\r\n\r\n-- Tipo de dato algebraico de las pilas:\r\ndata Pila a = Vacia\r\n            | P a (Pila a)\r\n            deriving Eq\r\n\r\ninstance (Show a) => Show (Pila a) where\r\n    showsPrec p Vacia cad   = showChar '-' cad\r\n    showsPrec p (P x s) cad = shows x (showChar '|' (shows s cad))\r\n\r\n-- Ejemplo de pila:\r\n--    *Pila> p1\r\n--    1|2|3|-\r\np1 = apilar 1 (apilar 2 (apilar 3 pilaVacia))\r\n\r\n-- pilaVacia es la pila vac\u00eda. Por ejemplo,\r\n--    > pilaVacia\r\n--    -\r\npilaVacia :: Pila a\r\npilaVacia = Vacia\r\n\r\n-- (esPilaVacia p) se verifica si p es la pila vac\u00eda. Por ejemplo,\r\n--    esPilaVacia p1         ==  False\r\n--    esPilaVacia pilaVacia  ==  True\r\nesPilaVacia :: Pila a -> Bool\r\nesPilaVacia Vacia = True\r\nesPilaVacia _     = False\r\n\r\n-- (apilar x p) es la pila obtenida a\u00f1adi\u00e9ndole x encima de la pila\r\n-- p. Por ejemplo,\r\n--    apilar 4 p1  =>  4|1|2|3|-\r\napilar :: a -> Pila a -> Pila a\r\napilar x p = P x p\r\n\r\n-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila\r\n-- p. Por ejemplo,\r\n--    desapilar p1  =>  2|3|-\r\ndesapilar :: Pila a -> Pila a\r\ndesapilar Vacia   = error \"no se puede desapilar la pila vacia\"\r\ndesapilar (P _ p) = p\r\n\r\n-- (cima p) es la cima de la pila p. Por ejemplo,\r\n--    cima p1  =>  1\r\ncima :: Pila a -> a\r\ncima Vacia   = error \"la pila vacia no tiene cima\"\r\ncima (P x _) =  x\r\n<\/pre>\n<h3><i>PilaConListas.hs<\/i>: Implemetaci\u00f3n de las pilas mediante listas<\/h3>\n<pre lang=\"haskell\">\r\nmodule PilaConListas\r\n    (Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where\r\n\r\nimport qualified Pila\r\n\r\n-- Pilas como listas\r\nnewtype Pila a = P [a]\r\n     deriving Eq\r\n\r\n-- Escritura de las pilas.\r\ninstance (Show a) => Show (Pila a) where\r\n    showsPrec p (P [])     cad = showChar '-' cad\r\n    showsPrec p (P (x:xs)) cad\r\n        = shows x (showChar '|' (shows (P xs) cad))\r\n\r\n-- Ejemplo de pila:\r\n--    > p1\r\n--    1|2|3|-\r\np1 = apilar 1 (apilar 2 (apilar 3 pilaVacia))\r\n\r\n-- pilaVacia es la pila vac\u00eda. Por ejemplo,\r\n--    > pilaVacia\r\n--    -\r\npilaVacia :: Pila a\r\npilaVacia = P []\r\n\r\n-- (esPilaVacia p) se verifica si p es la pila vac\u00eda. Por ejemplo,\r\n--    esPilaVacia p1         ==  False\r\n--    esPilaVacia pilaVacia  ==  True\r\nesPilaVacia :: Pila a -> Bool\r\nesPilaVacia (P []) = True\r\nesPilaVacia (P _ ) = False\r\n\r\n-- (apilar x p) es la pila obtenida a\u00f1adi\u00e9ndole x encima de la pila\r\n-- p. Por ejemplo,\r\n--    apilar 4 p1  =>  4|1|2|3|-\r\napilar :: a -> Pila a -> Pila a\r\napilar x (P xs) = P (x:xs)\r\n\r\n-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila\r\n-- p. Por ejemplo,\r\n--    desapilar p1  =>  2|3|-\r\ndesapilar :: Pila a -> Pila a\r\ndesapilar (P [])     = error \"desapilar from an empty stack\"\r\ndesapilar (P (_:xs)) = P  xs\r\n\r\n-- (cima p) es la cima de la pila p. Por ejemplo,\r\n--    cima p1  ==  1\r\ncima :: Pila a -> a\r\ncima (P [])    = error \"cima from an empty stack\"\r\ncima (P (x:_)) = x\r\n<\/pre>\n<h3><i>PilaPropiedades.hs<\/i>: Propiedades de las pilas<\/h3>\n<pre lang=\"haskell\">\r\nimport PilaConTipoDeDatoAlgebraico\r\n-- import PilaConListas\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de pilas                                          --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- genPila es un generador de pilas. Por ejemplo,\r\n--    *Main> sample genPila\r\n--    -\r\n--    0|0|-\r\n--    -\r\n--    -6|4|-3|3|0|-\r\n--    -\r\n--    9|5|-1|-3|0|-8|-5|-7|2|-\r\n--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-\r\n--    2|-14|-5|2|-\r\n--    5|9|-\r\n--    -1|-14|5|-\r\n--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-\r\ngenPila :: Arbitrary a => Gen (Pila a)\r\ngenPila = do xs <- listOf arbitrary\r\n             return (foldr apilar pilaVacia xs)\r\n  \r\n-- El tipo pila es una instancia del arbitrario. \r\ninstance (Arbitrary a, Num a) => Arbitrary (Pila a) where\r\n    arbitrary = genPila\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedad 1. La cima de la pila que resulta de apilar x en una pila p\r\n-- es x \r\n--    > quickCheck propCimaApilar\r\n--    +++ OK, passed 100 tests.\r\npropCimaApilar x p = \r\n    cima (apilar x p) == x\r\n\r\n-- Propiedad 2. La pila que resulta de desapilar despu\u00e9s de apilar\r\n-- cualquier elemento es la pila inicial.\r\n--    > quickCheck propDesapilarApilar\r\n--    +++ OK, passed 100 tests.\r\npropDesapilarApilar x p = \r\n    desapilar (apilar x p) == p\r\n\r\n-- Propiedad 3. La pila vac\u00eda est\u00e1 vac\u00eda.\r\n--    > quickCheck propVaciaEsvacia\r\n--    +++ OK, passed 100 tests.\r\npropVaciaEsvacia = esPilaVacia pilaVacia\r\n\r\n-- Propiedad 4. La pila que resulta de apilar un elemento en un pila\r\n-- cualquiera no es vac\u00eda.\r\n--    > quickCheck propApilarNoEsvacia\r\n--    +++ OK, passed 100 tests.\r\npropApilarNoEsvacia x p = not (esPilaVacia (apilar x p))\r\n\r\n-- todasPropiedades verifica toada las propiedades anteriores.\r\n--    *Main> quickCheck todasPropiedades\r\n--    +++ OK, passed 100 tests.\r\ntodasPropiedades x p =\r\n    propCimaApilar x p &&\r\n    propDesapilarApilar x p &&\r\n    propVaciaEsvacia &&\r\n    propApilarNoEsvacia x p\r\n<\/pre>\n<p>\nEl objetivo de la serie es la elaboraci\u00f3n del tema de TAD del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\">Inform\u00e1tica del Grado en Matem\u00e1ticas<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En este art\u00edculo contin\u00fao la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las pilas. En art\u00edculos anteriores present\u00e9 los TAD de los polinomios y el de los conjuntos. En \u00e9ste voy a presentar el TAD de las pilas y sus implementaciones en Haskell. Al igual que hice&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","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":[270,147,126,124],"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\/840"}],"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=840"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/840\/revisions"}],"predecessor-version":[{"id":2986,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/840\/revisions\/2986"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=840"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=840"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=840"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}