{"id":1170,"date":"2011-02-01T05:44:56","date_gmt":"2011-02-01T05:44:56","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1170"},"modified":"2013-03-08T05:50:03","modified_gmt":"2013-03-08T05:50:03","slug":"el-tipo-abstracto-de-datos-de-las-colas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-las-colas-en-haskell\/","title":{"rendered":"El tipo abstracto de datos de las colas en Haskell"},"content":{"rendered":"<p>En 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 colas.<\/p>\n<p>Al 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> Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operaci\u00f3n de inserci\u00f3n se realiza por un extremo (el posterior o final) y la operaci\u00f3n de extracci\u00f3n por el otro (el anterior o frente). Las colas tambi\u00e9n se llaman estructuras FIFO (del ingl\u00e9s First In First Out), debido a que el primer elemento en entrar ser\u00e1 tambi\u00e9n el primero en salir. Este comportamiento es an\u00e1logo a las colas del cine.<\/p>\n<p>El contenido del resto del art\u00edculo es el siguiente: <\/p>\n<ul>\n<li>la signatura del TAD de las colas;\n<li>las propiedades del TAD de las colas;\n<li>la implementaci\u00f3n, en Haskell, de las colas mediante listas;\n<li>la implementaci\u00f3n, en Haskell, de las colas mediante pares de listas y\n<li>la comprobaci\u00f3n con QuickCheck de sus propiedades.\n<\/ul>\n<p><!--more--><\/p>\n<h3>La signatura del TAD de las colas<\/h3>\n<p>Las signatura de las operaciones del TAD de las colas son las siguientes:<\/p>\n<pre lang=\"haskell\">\r\ncolaVacia   :: Cola a\r\nencolar     :: a -> Cola a -> Cola a\r\ncabeza      :: Cola a -> a\r\ndesencolar  :: Cola a -> Cola a\r\nesColaVacia :: Cola a -> Bool\r\nvalida      :: Cola a -> Bool\r\n<\/pre>\n<p>con el siguiente significado<\/p>\n<ul>\n<li> <i>colaVacia<\/i> es la cola vac\u00eda.\n<li> <i>(encolar x c)<\/i> es la cola obtenida a\u00f1adiendo el elemento x al final de la cola c.\n<li> <i>(cabeza c)<\/i> es la cabeza de la cola c.\n<li> <i>(desencolar c)<\/i> es la cola obtenida eliminando la cabeza de la cola c.\n<li> <i>(esColaVacia c)<\/i> se verifica si c es la cola vac\u00eda.\n<li> <i>(valida c)<\/i> se verifica si c representa una cola v\u00e1lida.\n<\/ul>\n<h3>Propiedades del TAD de las colas<\/h3>\n<p>Las propiedades son las siguientes:<\/p>\n<ol>\n<li> <tt>cabeza (encolar x colaVacia) == x<\/tt>\n<li> Si <tt>c<\/tt> es una cola no vac\u00eda, entonces <tt>cabeza (encolar x c) == cabeza c<\/tt>,\n<li> <tt>desencolar (encolar x colaVacia) == colaVacia<\/tt>\n<li> Si <tt>c<\/tt> es una cola no vac\u00eda, entonces <tt>desencolar (encolar x c) == encolar x (desencolar c)<\/tt>\n<li> <tt>esColaVacia colaVacia<\/tt>\n<li> <tt>not (esColaVacia (encolar x c))<\/tt>\n<\/ol>\n<h3><i>ColaConListas.hs<\/i>: Implementaci\u00f3n de las colas mediante listas<\/h3>\n<pre lang=\"haskell\">\r\nmodule ColaConListas \r\n    (Cola,\r\n     vacia,   -- Cola a\r\n     inserta, -- a -> Cola a -> Cola a\r\n     primero, -- Cola a -> a\r\n     resto,   -- Cola a -> Cola a\r\n     esVacia, -- Cola a -> Bool\r\n     valida   -- Cola a -> Bool\r\n    ) where\r\n\r\n-- Colas como listas:\r\nnewtype Cola a = C [a]\r\n    deriving (Show, Eq)\r\n\r\n-- Ejemplo de cola\r\n--    ghci> c1\r\n--    C [10,9,8,7,6,5,4,3,2,1]\r\nc1 = foldr inserta vacia [1..10]\r\n\r\n-- vacia es la cola vac\u00eda. Por ejemplo,\r\n--    ghci> vacia\r\n--    C []\r\nvacia :: Cola a\r\nvacia = C []\r\n\r\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\r\n-- c. Por ejemplo,\r\n--    inserta 12 c1  ==  C [10,9,8,7,6,5,4,3,2,1,12]\r\ninserta :: a -> Cola a -> Cola a\r\ninserta x (C c) = C (c ++ [x])\r\n\r\n-- Nota: La operaci\u00f3n inserta usa O(n) pasos.\r\n\r\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\r\n--    primero c1  ==  10\r\nprimero :: Cola a -> a\r\nprimero (C (x:_)) = x\r\nprimero (C [])    = error \"primero: cola vacia\"\r\n\r\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\r\n-- cola c. Por ejemplo,\r\n--    resto c1  ==  C [9,8,7,6,5,4,3,2,1]\r\nresto :: Cola a -> Cola a\r\nresto (C (_:xs)) = C xs\r\nresto (C [])     = error \"resto: cola vacia\"\r\n\r\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\r\n--    esVacia c1     ==  False\r\n--    esVacia vacia  ==  True\r\nesVacia :: Cola a -> Bool\r\nesVacia (C xs)  = null xs\r\n\r\n-- (valida c) se verifica si c representa una cola v\u00e1lida. Con esta\r\n-- representaci\u00f3n, todas las colas son v\u00e1lidas.\r\nvalida :: Cola a -> Bool\r\nvalida c = True\r\n<\/pre>\n<h3><i>ColaConDosListas.hs<\/i>: Implementaci\u00f3n de las colas mediante dos listas<\/h3>\n<p>En esta implementaci\u00f3n, una cola c se representa mediante un par de listas (xs,ys) de modo que los elementos de c son, en ese orden, los elementos de la lista xs++(reverse ys).<\/p>\n<p>Al dividir la lista en dos parte e invertir la segunda de ellas, esperamos hacer m\u00e1s eficiente las operaciones sobre las colas.<\/p>\n<p>Impondremos tambi\u00e9n una restricci\u00f3n adicional sobre la representaci\u00f3n: las colas ser\u00e1n representadas mediante pares (xs,ys) tales que si xs es vac\u00eda, entonces ys ser\u00e1 tambi\u00e9n vac\u00eda. Esta restricci\u00f3n ha de mantenerse por los programas que crean colas.<\/p>\n<pre lang=\"haskell\">\r\nmodule ColaConDosListas\r\n    (Cola,\r\n     vacia,   -- Cola a\r\n     inserta, -- a -> Cola a -> Cola a\r\n     primero, -- Cola a -> a\r\n     resto,   -- Cola a -> Cola a\r\n     esVacia, -- Cola a -> Bool\r\n     valida   -- Cola a -> Bool\r\n    ) where\r\n\r\n-- Las colas como pares listas.\r\nnewtype Cola a = C ([a],[a])\r\n    -- deriving Show\r\n\r\n-- Procedimiento de escritura de colas como pares de listas.\r\ninstance (Show a) => Show (Cola a) where\r\n    showsPrec p (C (xs,ys)) cad\r\n        = showString \"C \" (showList (xs ++ ys) cad)\r\n\r\n-- Ejemplo de cola: c1 es la cola obtenida a\u00f1adi\u00e9ndole a la cola \r\n-- vac\u00eda los n\u00fameros del 1 al 10. Por ejemplo,\r\n--    ghci> c1\r\n--    C [10,9,8,7,6,5,4,3,2,1]\r\nc1 :: Cola Int\r\nc1 = foldr inserta vacia [1..10]\r\n\r\n-- vacia es la cola vac\u00eda. Por ejemplo,\r\n--    ghci> vacia\r\n--    C []\r\nvacia :: Cola a\r\nvacia  = C ([],[])\r\n\r\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\r\n-- c. Por ejemplo,\r\n--    inserta 12 c1  ==  C [10,9,8,7,6,5,4,3,2,1,12]\r\ninserta :: a -> Cola a -> Cola a\r\ninserta y (C (xs,ys)) = C (normaliza (xs,y:ys))\r\n\r\n-- (normaliza p) es la cola obtenida al normalizar el par de listas\r\n-- p. Por ejemplo,  \r\n--    normaliza ([],[2,5,3])   ==  ([3,5,2],[])\r\n--    normaliza ([4],[2,5,3])  ==  ([4],[2,5,3])\r\nnormaliza :: ([a],[a]) -> ([a],[a])\r\nnormaliza ([], ys) = (reverse ys, [])\r\nnormaliza p        = p\r\n\r\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\r\n--    primero c1  ==  10\r\nprimero  :: Cola a -> a\r\nprimero (C (x:xs,ys)) = x\r\nprimero _             = error \"primero: cola vacia\"\r\n\r\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\r\n-- cola c. Por ejemplo,\r\n--    resto c1  ==  C [9,8,7,6,5,4,3,2,1]\r\nresto  :: Cola a -> Cola a\r\nresto (C ([],[]))   = error \"resto: cola vacia\"\r\nresto (C (x:xs,ys)) = C (normaliza (xs,ys))\r\n\r\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\r\n--    esVacia c1     ==  False\r\n--    esVacia vacia  ==  True\r\nesVacia :: Cola a -> Bool\r\nesVacia (C (xs,_)) = null xs\r\n\r\n-- (valida c) se verifica si la cola c es v\u00e1lida; es decir, si\r\n-- su primer elemento es vac\u00edo entonces tambi\u00e9n lo es el segundo. Por\r\n-- ejemplo, \r\n--    valida (C ([2],[5]))  ==  True\r\n--    valida (C ([2],[]))   ==  True\r\n--    valida (C ([],[5]))   ==  False\r\nvalida:: Cola a -> Bool\r\nvalida (C (xs,ys)) = not (null xs) || null ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Igualdad de colas                                                  --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (elementos c) es la lista de los elementos de la cola c en el orden de\r\n-- la cola. Por ejemplo, \r\n--    elementos (C ([3,2],[5,4,7]))  ==  [3,2,7,4,5]\r\nelementos:: Cola a -> [a]\r\nelementos (C (xs,ys)) = xs ++ (reverse ys)\r\n\r\n-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por\r\n-- ejemplo, \r\n--    igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2]))   ==  True\r\n--    igualColas (C ([3,2],[5,4,7])) (C ([],[5,4,7,2,3]))  ==  False\r\nigualColas c1 c2 = \r\n    valida c1 && valida c2 && elementos c1 == elementos c2\r\n\r\ninstance (Eq a) => Eq (Cola a) where\r\n    (==) = igualColas\r\n<\/pre>\n<h3>Propiedades de las colas<\/h3>\n<pre lang=\"haskell\">\r\n-- Nota: Necesita framework que est\u00e1 en http:\/\/goo.gl\/8psHc\r\n\r\n{-# LANGUAGE FlexibleInstances #-}\r\n\r\n-- Hay que elegir una implementaci\u00f3n del TAD colas:\r\nimport ColaConListas\r\n-- import ColaConDosListas\r\n\r\nimport Data.List\r\nimport Test.Framework (defaultMain, testGroup)\r\nimport Test.Framework.Providers.QuickCheck2 (testProperty)\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de colas                                          --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- genCola es un generador de colas de enteros. Por ejemplo,\r\n--    ghci> sample genCola\r\n--    C ([],[])\r\n--    C ([],[])\r\n--    C ([],[])\r\n--    C ([],[])\r\n--    C ([7,8,4,3,7],[5,3,3])\r\n--    C ([],[])\r\n--    C ([1],[13])\r\n--    C ([18,28],[12,21,28,28,3,18,14])\r\n--    C ([47],[64,45,7])\r\n--    C ([8],[])\r\n--    C ([42,112,178,175,107],[])\r\ngenCola :: Gen (Cola Int)\r\ngenCola = frequency [(1, return vacia),\r\n                     (30, do n <- choose (10,100)\r\n                             xs <- vectorOf n arbitrary\r\n                             return (creaCola xs))]\r\n          where creaCola = foldr inserta vacia\r\n\r\n-- El tipo pila es una instancia del arbitrario.\r\ninstance Arbitrary (Cola Int) where\r\n    arbitrary = genCola\r\n\r\n-- Propiedad. Todo los elementos generados por genCola son colas\r\n-- v\u00e1lidas. \r\nprop_genCola_correcto :: Cola Int -> Bool\r\nprop_genCola_correcto c = valida c\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_genCola_correcto\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedad. El primero de la cola obtenida a\u00f1adiendo x a la cola vac\u00eda\r\n-- es x. \r\nprop_primero_inserta_vacia :: Int -> Bool\r\nprop_primero_inserta_vacia x = \r\n    primero (inserta x vacia) == x\r\n\r\n-- Comprobaci\u00f3n.\r\n--    > quickCheck prop_primero_inserta_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. Si una cola no est\u00e1 vac\u00eda, su primer elemento no var\u00eda al\r\n-- a\u00f1adirle un elemento. \r\nprop_primero_inserta_no_vacia :: Cola Int -> Int -> Int -> Bool\r\nprop_primero_inserta_no_vacia c x y =\r\n    primero (inserta x c') == primero c'\r\n    where c' = inserta y vacia\r\n\r\n-- Comprobaci\u00f3n.\r\n--    > quickCheck prop_primero_inserta_no_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. El resto de la cola obtenida insertando un elemento en la\r\n-- cola vac\u00eda es la cola vac\u00eda.  \r\nprop_resto_inserta_vacia :: Int -> Bool\r\nprop_resto_inserta_vacia x = \r\n    resto (inserta x vacia) == vacia\r\n\r\n-- Comprobaci\u00f3n.\r\n--    > quickCheck prop_resto_inserta_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. Las operaciones de inserta y resto conmutan.\r\nprop_resto_inserta_en_no_vacia :: Cola Int -> Int -> Int -> Bool\r\nprop_resto_inserta_en_no_vacia c x y =\r\n    resto (inserta x c') == inserta x (resto c')\r\n    where c' = inserta y c\r\n\r\n-- Comprobaci\u00f3n.\r\n--    > quickCheck prop_resto_inserta_en_no_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. vacia es una cola vac\u00eda.\r\nprop_vacia_es_vacia :: Bool\r\nprop_vacia_es_vacia = \r\n    esVacia vacia\r\n\r\n-- Comprobaci\u00f3n.\r\n--    > quickCheck prop_vacia_es_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. La cola obtenida insertando un elemento no es vac\u00eda.\r\nprop_inserta_no_es_vacia :: Int -> Cola Int -> Bool\r\nprop_inserta_no_es_vacia x c = \r\n    not (esVacia (inserta x c))\r\n\r\n-- Comprobaci\u00f3n\r\n--    > quickCheck prop_inserta_no_es_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades de la normalizaci\u00f3n                                    --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedad. La cola vac\u00eda es v\u00e1lida.\r\nprop_valida_vacia :: Bool\r\nprop_valida_vacia = valida vacia\r\n\r\n-- Comprobaci\u00f3n\r\n--    ghci> quickCheck prop_valida_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. Al a\u00f1adirle un elemento a una cola v\u00e1lida se obtiene otra\r\n-- cola v\u00e1lida. \r\nprop_valida_inserta :: Cola Int -> Int -> Property\r\nprop_valida_inserta c x =\r\n    valida c ==> valida (inserta x c)\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_valida_inserta\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. El resto de una cola v\u00e1lida y no vac\u00eda es una cola v\u00e1lida. \r\nprop_valida_resto :: Cola Int -> Property\r\nprop_valida_resto c =\r\n    valida c && not (esVacia c) ==> valida (resto c)\r\n\r\n-- Comprobaci\u00f3n\r\n--    *Main> quickCheck prop_valida_resto\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- compruebaPropiedades comprueba todas las propiedades con la\r\n-- plataforma de verificaci\u00f3n. Por ejemplo,\r\n--    ghci> compruebaPropiedades\r\n--    Propiedades del TAD cola\r\n--      P1: [OK, passed 100 tests]\r\n--      P2: [OK, passed 100 tests]\r\n--      P3: [OK, passed 100 tests]\r\n--      P4: [OK, passed 100 tests]\r\n--      P5: [OK, passed 100 tests]\r\n--      P6: [OK, passed 100 tests]\r\n--    Propiedades de validez:\r\n--      P7: [OK, passed 100 tests]\r\n--      P8: [OK, passed 100 tests]\r\n--      P9: [OK, passed 100 tests]\r\n--    \r\n--             Properties  Total      \r\n--     Passed  9           9          \r\n--     Failed  0           0          \r\n--     Total   9           9     \r\ncompruebaPropiedades = \r\n    defaultMain \r\n        [testGroup \"Propiedades del TAD cola\"\r\n          [testProperty \"P1\" prop_primero_inserta_vacia,\r\n           testProperty \"P2\" prop_primero_inserta_no_vacia,\r\n           testProperty \"P3\" prop_resto_inserta_vacia,\r\n           testProperty \"P4\" prop_resto_inserta_en_no_vacia,\r\n           testProperty \"P5\" prop_vacia_es_vacia,\r\n           testProperty \"P6\" prop_inserta_no_es_vacia],\r\n         testGroup \"Propiedades de normalizacion\" \r\n          [testProperty \"P7\" prop_valida_vacia,\r\n           testProperty \"P8\" prop_valida_inserta,\r\n           testProperty \"P9\" prop_valida_resto]]\r\n<\/pre>\n<p>\nEl objetivo de la serie es la elaboraci\u00f3n de los temas 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 colas. Al 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. Una cola es una estructura&#8230;<\/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":[169,270,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\/1170"}],"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=1170"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1170\/revisions"}],"predecessor-version":[{"id":2940,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1170\/revisions\/2940"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1170"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}