{"id":4831,"date":"2015-03-25T21:39:58","date_gmt":"2015-03-25T20:39:58","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4831"},"modified":"2015-03-25T21:39:58","modified_gmt":"2015-03-25T20:39:58","slug":"i1m2014-el-tipo-abstracto-de-datos-de-las-colas-de-prioridad-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-el-tipo-abstracto-de-datos-de-las-colas-de-prioridad-en-haskell\/","title":{"rendered":"I1M2014: El tipo abstracto de datos de las colas de prioridad en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha estudiado el tipo abstracto de las colas de prioridad, su implementaci\u00f3n en Haskell mediante listas y mot\u00edculos y la verificaci\u00f3n con QuickCheck de sus propiedades caracter\u00edsticas.<\/p>\n<p>Las transparencias usadas en la clase son las del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/temas\/tema-16t.pdf\">tema 16<\/a><br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/7299547' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\n<p>El c\u00f3digo de la implementaci\u00f3n de las colas de prioridad mediante listas es el siguiente<\/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-- Nota. resto usa O(1) pasos.\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<p>El c\u00f3digo de la implementaci\u00f3n de las colas de prioridad mediante listas es el siguiente<\/p>\n<pre lang=\"haskell\">\nmodule ColaDePrioridadConMonticulos \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\nimport qualified Monticulo as M\n\n-- Colas de prioridad mediante mont\u00edculos.\nnewtype CPrioridad a = CP (M.Monticulo a)\n    deriving (Eq, Show)\n\n-- Ejemplo de cola de prioridad\n--    *Main> cp1\n--    CP (M 1 2 \n--          (M 2 2 \n--             (M 9 1 VacioM VacioM) \n--             (M 7 1 VacioM VacioM)) \n--          (M 3 1 VacioM VacioM))\ncp1 :: CPrioridad Int\ncp1 = foldr inserta vacia [3,1,7,2,9]\n\n-- vacia es la cola de prioridad vac\u00eda. Por ejemplo,\n--    vacia  ==  CP Vacio\nvacia :: Ord a => CPrioridad a \nvacia = CP M.vacio\n\n-- (inserta x c) a\u00f1ade el elemento x a la cola de prioridad c. Por ejemplo, \n--    ghci> cp1\n--    CP (M 1 2 \n--          (M 2 2 \n--             (M 9 1 VacioM VacioM) \n--             (M 7 1 VacioM VacioM)) \n--          (M 3 1 VacioM VacioM))\n--    ghci> inserta 5 cp1\n--    CP (M 1 2 \n--          (M 2 2 \n--             (M 9 1 VacioM VacioM) \n--             (M 7 1 VacioM VacioM)) \n--          (M 3 1 \n--             (M 5 1 VacioM VacioM) VacioM))\ninserta :: Ord a => a -> CPrioridad a -> CPrioridad a \ninserta v (CP c) = CP (M.inserta v c)\n\n-- (primero c) es la cabeza de la cola de prioridad c. Por ejemplo,\n--    primero cp1  ==  1\nprimero :: Ord a => CPrioridad a -> a\nprimero (CP c) = M.menor c\n\n-- (resto c) elimina la cabeza de la cola de prioridad c. Por ejemplo, \n--    ghci> cp1\n--    CP (M 1 2 \n--          (M 2 2 \n--             (M 9 1 VacioM VacioM) \n--             (M 7 1 VacioM VacioM)) \n--          (M 3 1 VacioM VacioM))\n--    ghci> resto cp1\n--    CP (M 2 2 \n--          (M 9 1 VacioM VacioM) \n--          (M 3 1 \n--             (M 7 1 VacioM VacioM) VacioM))\nresto :: Ord a => CPrioridad a -> CPrioridad a\nresto (CP c) = CP (M.resto c)\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 c) = M.esVacio c\n\n-- (valida c) se verifica si c es una cola de prioridad v\u00e1lida. En la\n-- representaci\u00f3n mediante mont\u00edculo todas las colas de prioridad son\n-- v\u00e1lidas. \nvalida :: Ord a => CPrioridad a -> Bool\nvalida _ = True\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En 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, su implementaci\u00f3n en Haskell mediante listas y mot\u00edculos y la verificaci\u00f3n con QuickCheck de sus propiedades caracter\u00edsticas. Las transparencias usadas en la clase son las del tema 16<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[238],"tags":[244,270,305],"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\/4831"}],"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=4831"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4831\/revisions"}],"predecessor-version":[{"id":4832,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4831\/revisions\/4832"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4831"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4831"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4831"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}