{"id":2026,"date":"2012-04-10T16:04:16","date_gmt":"2012-04-10T16:04:16","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2026"},"modified":"2013-03-08T05:48:16","modified_gmt":"2013-03-08T05:48:16","slug":"i1m2011-el-tad-tipo-abstracto-de-datos-de-las-tablas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-el-tad-tipo-abstracto-de-datos-de-las-tablas-en-haskell\/","title":{"rendered":"I1M2011: El TAD (tipo abstracto de datos) de las tablas en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a  href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha estudiado el TAD (tipo abstracto de datos) de las tablas y 3 implementaciones en Haskell: como funciones, como listas de asociaci\u00f3n y como matrices.<\/p>\n<p> Una <a href=\"http:\/\/es.wikipedia.org\/wiki\/Matriz_%28programaci%C3%B3n%29\">tabla<\/a> (<a href=\"http:\/\/en.wikipedia.org\/wiki\/Array_data_structure\">array<\/a> en ingl\u00e9s y <a href=\"http:\/\/fr.wikipedia.org\/wiki\/Tableau_%28structure_de_donn%C3%A9es%29\">tableau<\/a> en franc\u00e9s) es una colecci\u00f3n de elementos (<i>valores<\/i>) a los que se accede mediante sus <i>\u00edndices<\/i>.<\/p>\n<p>El contenido de la clase ha sido el siguiente:<\/p>\n<ul>\n<li>la signatura del TAD de las tablas;\n<li>las propiedades del TAD de las tablas;\n<li>las implementaciones, en Haskell, de las tablas mediante funciones, listas de asociaci\u00f3n y matrices 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 tablas<\/h3>\n<p>Las signatura de las operaciones del TAD de las tablas son las siguientes:<\/p>\n<pre lang=\"haskell\">\r\ntabla    :: Eq i => [(i,v)] -> Tabla i v           \r\nvalor    :: Eq i => Tabla i v -> i -> v            \r\nmodifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v\r\n<\/pre>\n<p>con el siguiente significado<\/p>\n<ul>\n<li> <i>(tabla ivs)<\/i> es la tabla correspondiente a la lista de asociaci\u00f3n ivs (que es una lista de pares formados por los \u00edndices y los valores).\n<li> <i>(valor t i)<\/i> es el valor del \u00edndice i en la tabla t.\n<li> <i>(modifica (i,v) t)<\/i> es la tabla obtenida modificando en la tabla t el valor de i por v.\n<\/ul>\n<h3>Propiedades del TAD de las tablas<\/h3>\n<p>Las propiedades son las siguientes:<\/p>\n<ol>\n<li> <tt>modifica (i,v') (modifica (i,v) t) = modifica (i,v') t<\/tt>\n<li> Si <tt>i \/= i'<\/tt>, entonces<br \/>\n<tt>modifica (i',v') (modifica (i,v) t) = modifica (i,v) (modifica (i',v') t)<\/tt><\/p>\n<li> <tt>valor (modifica (i,v) t) i = v<\/tt>\n<li> Si <tt>i \/= i'<\/tt>, entonces<br \/>\n<tt>valor (modifica (i,v) (modifica (k',v') t)) i' = valor (modifica (k',v') t) i'<\/tt>\n<\/ol>\n<h3>Implementaci\u00f3n de las tablas mediante funciones<\/h3>\n<pre lang=\"haskell\">\r\nmodule TablaConFunciones  \r\n    (Tabla,\r\n     tabla,   -- Eq i => [(i,v)] -> Tabla i v           \r\n     valor,   -- Eq i => Tabla i v -> i -> v            \r\n     modifica -- Eq i => (i,v) -> Tabla i v -> Tabla i v\r\n    ) where\r\n\r\n-- Las tablas como funciones.\r\nnewtype Tabla i v = Tbl (i -> v)\r\n\r\n-- Procedimiento de escritura.\r\ninstance Show (Tabla i v) where\r\n    showsPrec _ _ cad = showString \"<<Una tabla>>\" cad\r\n\r\n-- Ejemplos de tablas:\r\n--    ghci> t1\r\n--    <<Una tabla>>\r\nt1 = tabla [(i,f i) | i <- [1..6] ] \r\n     where f x | x < 3     = x\r\n               | otherwise = 3-x\r\nt2 = tabla [(4,89), (1,90), (2,67)]\r\n    \r\n-- (valor t i) es el valor del \u00edndice i en la tabla t. Por ejemplo, \r\n--    valor t1 6  ==  -3\r\n--    valor t2 2  ==  67\r\n--    valor t2 5  ==  *** Exception: fuera de rango\r\nvalor :: Eq i => Tabla i v -> i -> v\r\nvalor (Tbl f) i = f i\r\n\r\n-- (modifica (i,v) t) es la tabla obtenida modificando en la tabla t el\r\n-- valor de i por v. Por ejemplo, \r\n--    valor t1 6                   ==  -3\r\n--    valor (modifica (6,9) t1) 6  ==  9\r\nmodifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v\r\nmodifica (i,v) (Tbl f) = Tbl g\r\n    where g j | j == i    = v\r\n              | otherwise = f j\r\n\r\n-- (tabla ivs) es la tabla correspondiente a la lista de asociaci\u00f3n\r\n-- ivs (que es una lista de pares formados por los \u00edndices y los\r\n-- valores). Por ejemplo,\r\n--    ghci> tabla [(4,89), (1,90), (2,67)]\r\n--    <<Una tabla>>\r\ntabla :: Eq i => [(i,v)] -> Tabla i v\r\ntabla ivs = \r\n    foldr modifica \r\n          (Tbl (\\_ -> error \"fuera de rango\"))\r\n          ivs\r\n<\/pre>\n<h3>Implementaci\u00f3n de las tablas mediante listas de asociaci\u00f3n<\/h3>\n<pre lang=\"haskell\">\r\nmodule TablaConListasDeAsociacion \r\n    (Tabla,\r\n     tabla,   -- Eq i => [(i,v)] -> Tabla i v           \r\n     valor,   -- Eq i => Tabla i v -> i -> v            \r\n     modifica -- Eq i => (i,v) -> Tabla i v -> Tabla i v\r\n    ) where\r\n\r\n-- Las tablas como listas de asociaci\u00f3n.\r\nnewtype Tabla i v = Tbl [(i,v)]\r\n    deriving Show\r\n\r\n-- Ejemplos de tabla:\r\n--    ghci> t1\r\n--    Tbl [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)]\r\n--    ghci> t2\r\n--    Tbl [(4,89),(1,90),(2,67)]\r\nt1 = tabla [(i,f i) | i <- [1..6] ] \r\n     where f x | x < 3     = x\r\n               | otherwise = 3-x\r\nt2 = tabla [(4,89), (1,90), (2,67)]\r\n    \r\n-- (tabla ivs) es la tabla correspondiente a la lista de asociaci\u00f3n\r\n-- ivs (que es una lista de pares formados por los \u00edndices y los\r\n-- valores). Por ejemplo,\r\n--    tabla [(4,89), (1,90), (2,67)]  ==  Tbl [(4,89),(1,90),(2,67)]\r\ntabla :: Eq i => [(i,v)] -> Tabla i v\r\ntabla ivs = Tbl ivs\r\n\r\n-- (valor t i) es el valor del \u00edndice i en la tabla t. Por ejemplo, \r\n--    valor t1 6  ==  -3\r\n--    valor t2 2  ==  67\r\n--    valor t2 5  ==  *** Exception: fuera de rango\r\nvalor :: Eq i => Tabla i v -> i -> v\r\nvalor (Tbl []) i = error \"fuera de rango\"\r\nvalor (Tbl ((j,v):r)) i\r\n     | i == j    = v\r\n     | otherwise = valor (Tbl r) i \r\n\r\n-- (modifica (i,x) t) es la tabla obtenida modificando en la tabla t el\r\n-- valor de i por x. Por ejemplo, \r\n--    valor t1 6                   ==  -3\r\n--    valor (modifica (6,9) t1) 6  ==  9\r\nmodifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v\r\nmodifica p (Tbl []) = (Tbl [p])\r\nmodifica p'@(i,_) (Tbl (p@(j,_):r))\r\n     | i == j     = Tbl (p':r)\r\n     | otherwise  = Tbl (p:r')\r\n     where Tbl r' = modifica p' (Tbl r)\r\n\r\n-- Nota sobre la eficiencia: \r\n-- * modifica y valor son de O(n) pasos en el peor caso,\r\n--   donde n es el n\u00famero de entradas en la tabla. \r\n-- * modifica requiere O(n) celdas en el peor caso.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Igualdad                                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n--- Las tablas son comparables por igualdad.\r\ninstance (Eq i, Eq v) => Eq (Tabla i v) where\r\n    (Tbl [])        == (Tbl []) = True\r\n    (Tbl ((i,v):t)) == Tbl t'   = elem (i,v) t' && \r\n                                  Tbl t == Tbl [p | p <- t', p \/= (i,v)]\r\n<\/pre>\n<h3>Implementaci\u00f3n de las tablas mediante matrices<\/h3>\n<pre lang=\"haskell\">\r\nmodule TablaConMatrices \r\n    (Tabla,\r\n     tabla,     -- Eq i => [(i,v)] -> Tabla i v           \r\n     valor,     -- Eq i => Tabla i v -> i -> v            \r\n     modifica,  -- Eq i => (i,v) -> Tabla i v -> Tabla i v\r\n     tieneValor -- Ix i => Tabla i v -> i -> Bool\r\n    ) where\r\n\r\nimport Data.Array (Array, Ix, array, (\/\/), (!), bounds, inRange)\r\n\r\n-- Las tablas como matrices.\r\nnewtype Tabla i v = Tbl (Array i v)\r\n    deriving (Show, Eq)\r\n\r\n-- Ejemplos de tablas:\r\n--    ghci> t1\r\n--    Tbl (array (1,6) [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)])\r\n--    ghci> t2\r\n--    Tbl (array (1,3) [(1,5),(2,4),(3,7)])\r\nt1 = tabla [(i,f i) | i <- [1..6] ] \r\n     where f x | x < 3     = x\r\n               | otherwise = 3-x\r\nt2 = tabla [(1,5),(2,4),(3,7)]\r\n    \r\n-- (tabla ivs) es la tabla correspondiente a la lista de asociaci\u00f3n\r\n-- ivs (que es una lista de pares formados por los \u00edndices y los\r\n-- valores). Por ejemplo,\r\n--    ghci> tabla [(1,5),(3,7),(2,4)]\r\n--    Tbl (array (1,3) [(1,5),(2,4),(3,7)])\r\ntabla :: Ix i => [(i,v)] -> Tabla i v\r\ntabla ivs = Tbl (array (m,n) ivs)\r\n    where indices = [i | (i,_) <- ivs]\r\n          m       = minimum indices\r\n          n       = maximum indices\r\n\r\n-- (valor t i) es el valor del \u00edndice i en la tabla t. Por ejemplo, \r\n--    valor t1 6  ==  -3\r\n--    valor t2 2  ==   4\r\n--    valor t2 5  ==  *** Exception: Index (5) out of range ((1,3))\r\nvalor :: Ix i => Tabla i v -> i -> v\r\nvalor (Tbl t) i = t ! i\r\n\r\n-- (modifica (i,x) t) es la tabla obtenida modificando en la tabla t el\r\n-- valor de i por x. Por ejemplo, \r\n--    valor t1 6                   ==  -3\r\n--    valor (modifica (6,9) t1) 6  ==  9\r\nmodifica :: Ix i => (i,v) -> Tabla i v -> Tabla i v\r\nmodifica p (Tbl t) = Tbl (t \/\/ [p])\r\n\r\n-- (cotas t) son las cotas de la tabla t. Por ejemplo,\r\n--    t2        ==  Tbl (array (1,3) [(1,5),(2,4),(3,7)])\r\n--    cotas t2  ==  (1,3)\r\ncotas :: Ix i => Tabla i v -> (i,i)\r\ncotas (Tbl t) = bounds t\r\n\r\n-- (tieneValor t x) se verifica si x es una clave de la tabla t. Por ejemplo,\r\n--    tieneValor t2 3  ==  True\r\n--    tieneValor t2 4  ==  False\r\ntieneValor :: Ix i => Tabla i v -> i -> Bool\r\ntieneValor t = inRange (cotas t)\r\n<\/pre>\n<h3>Propiedades de las tablas<\/h3>\n<pre lang=\"haskell\">\r\n{-# LANGUAGE FlexibleInstances #-}\r\n\r\n-- Nota: Hay que elegir una implementaci\u00f3n del TAD tabla:\r\nimport TablaConListasDeAsociacion\r\n-- import TablaConMatrices (Pendiente de depurar)\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generadores de tablas                                              --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- genTabla es un generador de tablas. Por ejemplo,\r\n--    ghci> sample genTabla\r\n--    Tbl [(1,0)]\r\n--    Tbl [(1,-1)]\r\n--    Tbl [(1,0),(2,-1),(3,1),(4,1),(5,0)]\r\n--    Tbl [(1,1),(2,-1),(3,-1),(4,3)]\r\n--    Tbl [(1,3),(2,-5),(3,-7),(4,-2),(5,-8)]\r\n--    Tbl [(1,16),(2,-6),(3,-13),(4,-7),(5,2),(6,11)]\r\n--    Tbl [(1,-4),(2,-1),(3,3),(4,5)]\r\n--    Tbl [(1,-8),(2,16),(3,32)]\r\ngenTabla :: Gen (Tabla Int Int)\r\ngenTabla = \r\n    do x <- arbitrary\r\n       xs <- listOf arbitrary\r\n       return (tabla (zip [1..] (x:xs)))\r\n\r\n-- Las tablas son concreciones de los arbitrarios.\r\ninstance Arbitrary (Tabla Int Int) where\r\n    arbitrary = genTabla\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades                                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedades de modifica\r\n-- -----------------------\r\n\r\n-- Propiedad. Al modificar una tabla dos veces con la misma clave se\r\n-- obtiene el mismos resultado que modificarla una vez con el \u00faltimo\r\n-- valor. \r\nprop_modifica_modifica_1 :: Int -> Int -> Int -> Tabla Int Int -> Bool\r\nprop_modifica_modifica_1 i v v' t =\r\n    modifica (i,v') (modifica (i,v) t) \r\n    == modifica (i,v') t \r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_modifica_modifica_1\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. Al modificar una tabla con dos pares con claves distintas\r\n-- no importa el orden en que se a\u00f1adan los pares. \r\nprop_modifica_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int \r\n                              -> Property\r\nprop_modifica_modifica_2 i i' v v' t =\r\n    i \/= i' ==>\r\n    modifica (i',v') (modifica (i,v) t) \r\n    == modifica (i,v) (modifica (i',v') t) \r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_modifica_modifica_2\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedades de valor\r\n-- --------------------\r\n\r\n-- Propiedad. El valor de la clave i en la tabla obtenida a\u00f1adi\u00e9ndole el\r\n-- par (i,v) a la tabla t es v.\r\nprop_valor_modifica_1 :: Int -> Int -> Tabla Int Int -> Bool\r\nprop_valor_modifica_1 i v t =\r\n    valor (modifica (i,v) t) i == v\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_valor_modifica_1\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. Sean i y i' dos claves distintas. El valor de la clave i'\r\n-- en la tabla obtenida a\u00f1adi\u00e9ndole el par (i,v) a la tabla t' (que\r\n-- contiene la clave i') es el valor de i' en t'. \r\nprop_valor_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int \r\n                            -> Property\r\nprop_valor_modifica_2 i v i' v' t =\r\n    i \/= i' ==>\r\n    valor (modifica (i,v) t') i' == valor t' i'\r\n    where t' = modifica (i',v') t\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_valor_modifica_2\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 19-39 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-18t.pdf\">tema 18<\/a>:<br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/7382408' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\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 TAD (tipo abstracto de datos) de las tablas y 3 implementaciones en Haskell: como funciones, como listas de asociaci\u00f3n y como matrices. Una tabla (array en ingl\u00e9s y tableau en franc\u00e9s) es una colecci\u00f3n de elementos (valores) a&#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":[1],"tags":[295],"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\/2026"}],"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=2026"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2026\/revisions"}],"predecessor-version":[{"id":2826,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2026\/revisions\/2826"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2026"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2026"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2026"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}