{"id":5335,"date":"2016-03-02T13:03:24","date_gmt":"2016-03-02T12:03:24","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5335"},"modified":"2016-03-03T13:04:38","modified_gmt":"2016-03-03T12:04:38","slug":"i1m2015-el-tipo-abstracto-de-datos-de-las-colas-de-prioridad-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-el-tipo-abstracto-de-datos-de-las-colas-de-prioridad-en-haskell\/","title":{"rendered":"I1M2015: El tipo abstracto de datos de las colas de prioridad en Haskell"},"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 ha estudiado el tipo abstracto de las colas de prioridad.<\/p>\n<p>Se ha seguido el mismo patr\u00f3n que en los anteriores tipos de datos:<\/p>\n<ul>\n<li>elecci\u00f3n de las operaciones b\u00e1sicas,<\/li>\n<li>especificaci\u00f3n de sus propiedades,<\/li>\n<li>implementaci\u00f3n en Haskell mediante listas,<\/li>\n<li>an\u00e1lisis de la complejidad de las definiciones de las operaciones b\u00e1sicas y<\/li>\n<li>verificaci\u00f3n con QuickCheck de sus propiedades caracter\u00edsticas.<\/li>\n<\/ul>\n<p>Las transparencias usadas en la clase son las del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/temas\/tema-16.html\">tema 16<\/a><\/p>\n<p>El c\u00f3digo de la implementaci\u00f3n de las colas de prioridad mediante listas es el siguiente<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\nmodule ColaDePrioridadConListas\n    (CPrioridad,\n     vacia,   -- Ord a => CPrioridad a \n     inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a \n     primero, -- Ord a => CPrioridad a -> a\n     resto,   -- Ord a => CPrioridad a -> CPrioridad a\n     esVacia, -- Ord a => CPrioridad a -> Bool \n     valida   -- Ord a => CPrioridad a -> Bool\n    ) where\n\n-- Colas de prioridad mediante listas.\nnewtype CPrioridad a = CP [a]\n    deriving (Eq, Show)\n\n-- Ejemplo de cola de prioridad\n--    ghci> cp1\n--    CP [1,2,3,7,9]\ncp1 :: CPrioridad Int\ncp1 = foldr inserta vacia [3,1,7,2,9]\n\n-- (valida c) se verifica si c es una cola de prioridad v\u00e1lida. Por\n-- ejemplo, \n--    valida (CP [1,3,5])  ==  True\n--    valida (CP [1,5,3])  ==  False\nvalida :: Ord a => CPrioridad a -> Bool\nvalida (CP xs) = ordenada xs\n    where ordenada (x:y:zs) = x <= y &#038;&#038; ordenada (y:zs)\n          ordenada _        = True\n\n-- vacia es la cola de prioridad vac\u00eda. Por ejemplo,\n--    vacia  ==  CP []\nvacia :: Ord a => CPrioridad a \nvacia = CP []\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo el elemento x a la cola\n-- de prioridad c. Por ejemplo,  \n--    cp1            ==  CP [1,2,3,7,9]\n--    inserta 5 cp1  ==  CP [1,2,3,5,7,9]\ninserta :: Ord a => a -> CPrioridad a -> CPrioridad a \ninserta x (CP q) = CP (ins x q)\n    where ins x []                   = [x]\n          ins x r@(e:r') | x < e     = x:r\n                         | otherwise = e:ins x r'\n\n-- Nota. inserta usa O(n) pasos.\n\n-- (primero c) es el primer elemento de la cola de prioridad c. Por\n-- ejemplo, \n--    cp1          ==  CP [1,2,3,7,9]\n--    primero cp1  ==  1\nprimero :: Ord a => CPrioridad a -> a\nprimero (CP(x:_)) = x\nprimero _         = error \"primero: cola de prioridad vacia\"\n\n-- (resto c) es la cola de prioridad obtenida eliminando el primer\n-- elemento de la cola de prioridad c. Por ejemplo,  \n--    cp1        ==  CP [1,2,3,7,9]\n--    resto cp1  ==  CP [2,3,7,9]\nresto :: Ord a => CPrioridad a -> CPrioridad a\nresto (CP (_:xs)) = CP xs\nresto _           = error \"resto: cola de prioridad vacia\"\n\n-- (esVacia c) se verifica si la cola de prioridad c es vac\u00eda. Por\n-- ejemplo,   \n--    esVacia cp1    ==  False\n--    esVacia vacia  ==  True\nesVacia :: Ord a => CPrioridad a -> Bool \nesVacia (CP xs) = null xs\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 ha estudiado el tipo abstracto de las colas de prioridad. Se ha seguido el mismo patr\u00f3n que en los anteriores tipos de datos: elecci\u00f3n de las operaciones b\u00e1sicas, especificaci\u00f3n de sus propiedades, implementaci\u00f3n en Haskell mediante listas,&#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":[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\/5335"}],"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=5335"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5335\/revisions"}],"predecessor-version":[{"id":5336,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5335\/revisions\/5336"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}