{"id":1187,"date":"2011-02-08T06:03:50","date_gmt":"2011-02-08T06:03:50","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1187"},"modified":"2013-03-08T05:50:03","modified_gmt":"2013-03-08T05:50:03","slug":"el-tipo-abstracto-de-datos-de-las-colas-de-prioridad-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-las-colas-de-prioridad-en-haskell\/","title":{"rendered":"El tipo abstracto de datos de las colas de prioridad 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 de prioridad.<\/p>\n<p> Una <a href=\"http:\/\/en.wikipedia.org\/wiki\/Priority_queue\">cola de prioridad<\/a> (en ingl\u00e9s, <i>priority queue<\/i>) es una cola en la que cada elemento tiene asociada una prioridad y la operaci\u00f3n de extracci\u00f3n siempre elige el elemento de menor prioridad. Un ejemplo de cola de prioridad es el formado por una lista de ciudades ordenadas por su distancia a un destino final. <\/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 de prioridad;\n<li>las propiedades del TAD de las colas de prioridad;\n<li>la implementaci\u00f3n, en Haskell, de las colas de prioridad mediante listas y\n<li>la comprobaci\u00f3n con QuickCheck de sus propiedades.\n<\/ul>\n<p>Posteriormente, cuando se estudien los mont\u00edculos, se presentar\u00e1 otra implementaci\u00f3n de las colas de prioridad mediante mont\u00edculos.<br \/>\n<!--more--><\/p>\n<h3>La signatura del TAD de las colas de prioridad<\/h3>\n<p>Las signatura de las operaciones del TAD de las colas prioridad son las siguientes:<\/p>\n<pre lang=\"haskell\">\r\nvacia   :: Ord a => CPrioridad a \r\ninserta :: Ord a => a -> CPrioridad a -> CPrioridad a \r\nprimero :: Ord a => CPrioridad a -> a\r\nresto   :: Ord a => CPrioridad a -> CPrioridad a\r\nesVacia :: Ord a => CPrioridad a -> Bool \r\nvalida  :: Ord a => CPrioridad a -> Bool\r\n<\/pre>\n<p>con el siguiente significado<\/p>\n<ul>\n<li> <i>vacia<\/i> es la cola de prioridad vac\u00eda.\n<li> <i>(inserta x c)<\/i> a\u00f1ade el elemento x a la cola de<br \/>\n  prioridad c.<\/p>\n<li> <i>(primero c)<\/i> es el primer elemento de la cola de prioridad<br \/>\n  c. <\/p>\n<li> <i>(resto c)<\/i> es el resto de la cola de prioridad c.\n<li> <i>(esVacia c)<\/i> se verifica si la cola de prioridad c<br \/>\n  es vac\u00eda.<\/p>\n<li> <i>(valida c)<\/i> se verifica si c es una cola de prioridad<br \/>\n  v\u00e1lida.\n<\/ul>\n<h3>Propiedades del TAD de las colas de prioridad<\/h3>\n<p>Las propiedades son las siguientes:<\/p>\n<ol>\n<li> <tt>inserta x (inserta y c) = inserta y (inserta x c)<\/tt>\n<li> <tt>primero (inserta x vacia) = x<\/tt>\n<li> Si <tt>x <= y<\/tt>, entonces <tt>primero (inserta y (inserta x c)) = primero (inserta x c)<\/tt>\n<li> <tt>resto (inserta x vacia) = vacia<\/tt>\n<li> Si <tt>x <= y<\/tt>, entonces <tt>resto (inserta y (inserta x c)) = inserta y (resto (inserta x c))<\/tt>\n<li> <tt>esVacia vacia<\/tt>\n<li> <tt>not (esVacia (inserta x c))<\/tt>\n<\/ol>\n<h3>Implementaci\u00f3n de las colas de prioridad mediante listas<\/h3>\n<pre lang=\"haskell\">\r\nmodule ColaDePrioridadConListas\r\n    (CPrioridad,\r\n     vacia,   -- Ord a => CPrioridad a \r\n     inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a \r\n     primero, -- Ord a => CPrioridad a -> a\r\n     resto,   -- Ord a => CPrioridad a -> CPrioridad a\r\n     esVacia, -- Ord a => CPrioridad a -> Bool \r\n     valida   -- Ord a => CPrioridad a -> Bool\r\n    ) where\r\n\r\n-- Colas de prioridad mediante listas.\r\nnewtype CPrioridad a = CP [a]\r\n    deriving (Eq, Show)\r\n\r\n-- Ejemplo de cola de prioridad\r\n--    ghci> cp1\r\n--    CP [1,2,3,7,9]\r\ncp1 :: CPrioridad Int\r\ncp1 = foldr inserta vacia [3,1,7,2,9]\r\n\r\n-- (valida c) se verifica si c es una cola de prioridad v\u00e1lida. Por\r\n-- ejemplo, \r\n--    valida (CP [1,3,5])  ==  True\r\n--    valida (CP [1,5,3])  ==  False\r\nvalida :: Ord a => CPrioridad a -> Bool\r\nvalida (CP xs) = ordenada xs\r\n    where ordenada (x:y:zs) = x <= y &#038;&#038; ordenada (y:zs)\r\n          ordenada _        = True\r\n\r\n-- vacia es la cola de prioridad vac\u00eda. Por ejemplo,\r\n--    vacia  ==  CP []\r\nvacia :: Ord a => CPrioridad a \r\nvacia = CP []\r\n\r\n-- (inserta x c) es la cola obtenida a\u00f1adiendo el elemento x a la cola\r\n-- de prioridad c. Por ejemplo,  \r\n--    cp1            ==  CP [1,2,3,7,9]\r\n--    inserta 5 cp1  ==  CP [1,2,3,5,7,9]\r\ninserta :: Ord a => a -> CPrioridad a -> CPrioridad a \r\ninserta x (CP q) = CP (ins x q)\r\n    where ins x []                   = [x]\r\n          ins x r@(e:r') | x < e     = x:r\r\n                         | otherwise = e:ins x r'\r\n\r\n-- Nota. inserta usa O(n) pasos.\r\n\r\n-- (primero c) es el primer elemento de la cola de prioridad c. Por\r\n-- ejemplo, \r\n--    cp1          ==  CP [1,2,3,7,9]\r\n--    primero cp1  ==  1\r\nprimero :: Ord a => CPrioridad a -> a\r\nprimero (CP(x:_)) = x\r\nprimero _         = error \"primero: cola de prioridad vacia\"\r\n\r\n-- (resto c) es la cola de prioridad obtenida eliminando el primer\r\n-- elemento de la cola de prioridad c. Por ejemplo,  \r\n--    cp1        ==  CP [1,2,3,7,9]\r\n--    resto cp1  ==  CP [2,3,7,9]\r\nresto :: Ord a => CPrioridad a -> CPrioridad a\r\nresto (CP (_:xs)) = CP xs\r\nresto _           = error \"resto: cola de prioridad vacia\"\r\n\r\n-- Nota. resto usa O(1) pasos.\r\n\r\n-- (esVacia c) se verifica si la cola de prioridad c es vac\u00eda. Por\r\n-- ejemplo,   \r\n--    esVacia cp1    ==  False\r\n--    esVacia vacia  ==  True\r\nesVacia :: Ord a => CPrioridad a -> Bool \r\nesVacia (CP xs) = null xs\r\n<\/pre>\n<h3>Propiedades de las colas de prioridad<\/h3>\n<pre lang=\"haskell\">\r\nmodule ColaDePrioridadPropiedades where\r\n\r\n-- Nota: Hay que elegir una de las 2 implementaciones del TAD cola de\r\n-- prioridad. \r\nimport ColaDePrioridadConListas\r\n-- import ColaDePrioridadConMonticulos\r\n\r\nimport Test.QuickCheck\r\nimport Test.Framework (defaultMain, testGroup)\r\nimport Test.Framework.Providers.QuickCheck2 (testProperty)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de colas de prioridad\r\n-- ---------------------------------------------------------------------\r\n\r\n-- genCPrioridad es un generador de colas de prioridad. Por ejemplo,\r\n--    ghci> sample genCPrioridad\r\n--    CP []\r\n--    CP []\r\n--    CP [-4]\r\n--    CP [-2,-1,-1,2,5]\r\n--    CP [-8,-5,4,6,8]\r\n--    CP [-4,-1,3,3,6,7,10,10,10,10]\r\n--    CP [-12,-10,-9,-7,2,4,6,7,7,9]\r\n--    CP [-14,-12,-12,-7,-7,-4,4,9,14]\r\n--    CP [-10,-9,-5,14]\r\n--    CP [18]\r\n--    CP [-19,-17,-16,-15,-13,-13,-13,-12,-6,-5,-3,0,2,3,4,5,8,18]\r\ngenCPrioridad :: (Arbitrary a, Num a, Ord a) =>  Gen (CPrioridad a)\r\ngenCPrioridad = do xs <- listOf arbitrary\r\n                   return (foldr inserta vacia xs)\r\n\r\n-- La colas de prioridad son una concreci\u00f3n de la clase arbitraria. \r\ninstance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where\r\n    arbitrary = genCPrioridad\r\n\r\n-- Prop.: Las colas de prioridad producidas por genCPrioridad son\r\n-- v\u00e1lidas. \r\nprop_genCPrioridad_correcto ::  CPrioridad Int -> Bool\r\nprop_genCPrioridad_correcto c = valida c\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_genCPrioridad_correcto\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedad. Si se a\u00f1ade dos elementos a una cola de prioridad se\r\n-- obtiene la misma cola de prioridad idependientemente del orden en\r\n-- que se a\u00f1adan los elementos.\r\nprop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool\r\nprop_inserta_conmuta x y c =\r\n    inserta x (inserta y c) == inserta y (inserta x c)\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_inserta_conmuta\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. La cabeza de la cola de prioridad obtenida anadiendo un\r\n-- elemento x a la cola de prioridad vac\u00eda es x.\r\nprop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool\r\nprop_primero_inserta_vacia x c =\r\n    primero (inserta x vacia) == x\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_primero_inserta_vacia\r\n--    +++ OK, passed 100 tests.\r\n \r\n-- Propiedad. El primer elemento de una cola de prioridad c no cambia\r\n-- cuando se le a\u00f1ade un elemento mayor o igual que alg\u00fan elemento de c. \r\nprop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property\r\nprop_primero_inserta x y c =\r\n    x <= y ==> \r\n    primero (inserta y c') == primero c'\r\n    where c' = inserta x c\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_primero_inserta\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. El resto de a\u00f1adir un elemento a la cola de prioridad\r\n-- 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--    ghci> quickCheck prop_resto_inserta_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. El resto de la cola de prioridad obtenida a\u00f1adiendo un\r\n-- elemento y a una cola c' (que tiene alg\u00fan elemento menor o igual que\r\n-- y) es la cola que se obtiene a\u00f1adiendo y al resto de c'.\r\nprop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property\r\nprop_resto_inserta x y c =\r\n    x <= y ==> \r\n    resto (inserta y c') == inserta y (resto c')\r\n    where c' = inserta x c\r\n\r\n-- Comprobaci\u00f3n:\r\n--    ghci> quickCheck prop_resto_inserta\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 = esVacia (vacia :: CPrioridad Int)\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_vacia_es_vacia\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. Si se a\u00f1ade un elemento a una cola de prioridad se obtiene\r\n-- una cola no vac\u00eda.\r\nprop_inserta_no_es_vacia :: Int -> CPrioridad 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--    ghci> quickCheck prop_inserta_no_es_vacia\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--    Correcci\u00f3n del generador:\r\n--      P0: [OK, passed 100 tests]\r\n--    Propiedades de colas de prioridad:\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--      P7: [OK, passed 100 tests]\r\n--    \r\n--             Properties  Total      \r\n--     Passed  8           8          \r\n--     Failed  0           0          \r\n--     Total   8           8  \r\ncompruebaPropiedades = \r\n    defaultMain \r\n        [testGroup \"Correcci\u00f3n del generador\" \r\n          [testProperty \"P0\" prop_genCPrioridad_correcto],\r\n         testGroup \"Propiedades de colas de prioridad:\"\r\n          [testProperty \"P1\" prop_inserta_conmuta,\r\n           testProperty \"P2\" prop_primero_inserta_vacia,\r\n           testProperty \"P3\" prop_primero_inserta,\r\n           testProperty \"P4\" prop_resto_inserta_vacia,\r\n           testProperty \"P5\" prop_resto_inserta,\r\n           testProperty \"P6\" prop_vacia_es_vacia,\r\n           testProperty \"P7\" prop_inserta_no_es_vacia]]\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 de prioridad. Una cola de prioridad (en ingl\u00e9s, priority queue) es una cola en la que cada elemento tiene asociada una prioridad y la operaci\u00f3n de extracci\u00f3n siempre elige el elemento de menor&#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":[135,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\/1187"}],"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=1187"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1187\/revisions"}],"predecessor-version":[{"id":2936,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1187\/revisions\/2936"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}