{"id":4700,"date":"2015-01-07T21:22:58","date_gmt":"2015-01-07T20:22:58","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4700"},"modified":"2015-01-08T11:26:38","modified_gmt":"2015-01-08T10:26:38","slug":"i1m2014-el-tad-tipo-abstracto-de-datos-de-las-tablas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-el-tad-tipo-abstracto-de-datos-de-las-tablas-en-haskell\/","title":{"rendered":"I1M2014: El TAD (tipo abstracto de datos) de las tablas en Haskell"},"content":{"rendered":"<p>En la primera parte de la clase de hoy del curso 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 c\u00f3mo trabajar con tablas en Haskell usando el m\u00f3dulo Data.Array y en la segunda parte se ha estudiado el TAD (tipo abstracto de datos) de las tablas y tres implementaciones en Haskell: como funciones, como listas de asociaci\u00f3n y como matrices.<\/p>\n<p>Una <a href=\"http:\/\/en.wikipedia.org\/wiki\/Array_data_structure\">tabla<\/a> (<em>array<\/em> en ingl\u00e9s) es una colecci\u00f3n de elementos (<i>valores<\/i>) a los que se accede mediante sus <em>\u00edndices&lt;<\/em>.<\/p>\n<p>El contenido la segunda parte ha sido el siguiente:<\/p>\n<ul>\n<li>la signatura del TAD de las tablas;<\/li>\n<li>las propiedades del TAD de las tablas;<\/li>\n<li>las implementaciones, en Haskell, de las tablas mediante funciones, listas de asociaci\u00f3n y matrices y<\/li>\n<li>la comprobaci\u00f3n con QuickCheck de sus propiedades.<\/li>\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\">\ntabla    :: Eq i => [(i,v)] -> Tabla i v           \nvalor    :: Eq i => Tabla i v -> i -> v            \nmodifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v\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).<\/li>\n<li><i>(valor t i)<\/i> es el valor del \u00edndice i en la tabla t.<\/li>\n<li><i>(modifica (i,v) t)<\/i> es la tabla obtenida modificando en la tabla t el valor de i por v.<\/li>\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><\/li>\n<li>Si <tt>i \/= i'<\/tt>, entonces <tt>modifica (i',v') (modifica (i,v) t) = modifica (i,v) (modifica (i',v') t)<\/tt><\/li>\n<li><tt>valor (modifica (i,v) t) i = v<\/tt><\/li>\n<li>Si <tt>i \/= i'<\/tt>, entonces  <tt>valor (modifica (i,v) (modifica (k',v') t)) i' = valor (modifica (k',v') t) i'<\/tt><\/li>\n<\/ol>\n<h3>Implementaci\u00f3n de las tablas mediante funciones<\/h3>\n<pre lang=\"haskell\">\nmodule TablaConFunciones  \n    (Tabla,\n     tabla,   -- Eq i => [(i,v)] -> Tabla i v           \n     valor,   -- Eq i => Tabla i v -> i -> v            \n     modifica -- Eq i => (i,v) -> Tabla i v -> Tabla i v\n    ) where\n\n-- Las tablas como funciones.\nnewtype Tabla i v = Tbl (i -> v)\n\n-- Procedimiento de escritura.\ninstance Show (Tabla i v) where\n    showsPrec _ _ cad = showString \"<<Una tabla>>\" cad\n\n-- Ejemplos de tablas:\n--    ghci> t1\n--    <<Una tabla>>\nt1 = tabla [(i,f i) | i <- [1..6] ] \n     where f x | x < 3     = x\n               | otherwise = 3-x\nt2 = tabla [(4,89), (1,90), (2,67)]\n    \n-- (valor t i) es el valor del \u00edndice i en la tabla t. Por ejemplo, \n--    valor t1 6  ==  -3\n--    valor t2 2  ==  67\n--    valor t2 5  ==  *** Exception: fuera de rango\nvalor :: Eq i => Tabla i v -> i -> v\nvalor (Tbl f) i = f i\n\n-- (modifica (i,v) t) es la tabla obtenida modificando en la tabla t el\n-- valor de i por v. Por ejemplo, \n--    valor t1 6                   ==  -3\n--    valor (modifica (6,9) t1) 6  ==  9\nmodifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v\nmodifica (i,v) (Tbl f) = Tbl g\n    where g j | j == i    = v\n              | otherwise = f j\n\n-- (tabla ivs) es la tabla correspondiente a la lista de asociaci\u00f3n\n-- ivs (que es una lista de pares formados por los \u00edndices y los\n-- valores). Por ejemplo,\n--    ghci> tabla [(4,89), (1,90), (2,67)]\n--    <<Una tabla>>\ntabla :: Eq i => [(i,v)] -> Tabla i v\ntabla ivs = \n    foldr modifica \n          (Tbl (\\_ -> error \"fuera de rango\"))\n          ivs\n<\/pre>\n<h3>Implementaci\u00f3n de las tablas mediante listas de asociaci\u00f3n<\/h3>\n<pre lang=\"haskell\">\nmodule TablaConListasDeAsociacion \n    (Tabla,\n     tabla,   -- Eq i => [(i,v)] -> Tabla i v           \n     valor,   -- Eq i => Tabla i v -> i -> v            \n     modifica -- Eq i => (i,v) -> Tabla i v -> Tabla i v\n    ) where\n\n-- Las tablas como listas de asociaci\u00f3n.\nnewtype Tabla i v = Tbl [(i,v)]\n    deriving Show\n\n-- Ejemplos de tabla:\n--    ghci> t1\n--    Tbl [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)]\n--    ghci> t2\n--    Tbl [(4,89),(1,90),(2,67)]\nt1 = tabla [(i,f i) | i <- [1..6] ] \n     where f x | x < 3     = x\n               | otherwise = 3-x\nt2 = tabla [(4,89), (1,90), (2,67)]\n    \n-- (tabla ivs) es la tabla correspondiente a la lista de asociaci\u00f3n\n-- ivs (que es una lista de pares formados por los \u00edndices y los\n-- valores). Por ejemplo,\n--    tabla [(4,89), (1,90), (2,67)]  ==  Tbl [(4,89),(1,90),(2,67)]\ntabla :: Eq i => [(i,v)] -> Tabla i v\ntabla ivs = Tbl ivs\n\n-- (valor t i) es el valor del \u00edndice i en la tabla t. Por ejemplo, \n--    valor t1 6  ==  -3\n--    valor t2 2  ==  67\n--    valor t2 5  ==  *** Exception: fuera de rango\nvalor :: Eq i => Tabla i v -> i -> v\nvalor (Tbl []) i = error \"fuera de rango\"\nvalor (Tbl ((j,v):r)) i\n     | i == j    = v\n     | otherwise = valor (Tbl r) i \n\n-- (modifica (i,x) t) es la tabla obtenida modificando en la tabla t el\n-- valor de i por x. Por ejemplo, \n--    valor t1 6                   ==  -3\n--    valor (modifica (6,9) t1) 6  ==  9\nmodifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v\nmodifica p (Tbl []) = (Tbl [p])\nmodifica p1@(i,_) (Tbl (p@(j,_):r))\n     | i == j     = Tbl (p1:r)\n     | otherwise  = Tbl (p:r1)\n     where Tbl r1 = modifica p1 (Tbl r)\n\n-- Nota sobre la eficiencia: \n-- * modifica y valor son de O(n) pasos en el peor caso,\n--   donde n es el n\u00famero de entradas en la tabla. \n-- * modifica requiere O(n) celdas en el peor caso.\n\n-- ---------------------------------------------------------------------\n-- Igualdad                                                           --\n-- ---------------------------------------------------------------------\n\n--- Las tablas son comparables por igualdad.\ninstance (Eq i, Eq v) => Eq (Tabla i v) where\n    (Tbl [])        == (Tbl []) = True\n    (Tbl ((i,v):t)) == Tbl t1   = elem (i,v) t1 && \n                                  Tbl t == Tbl [p | p <- t1, p \/= (i,v)]\n<\/pre>\n<h3>Implementaci\u00f3n de las tablas mediante matrices<\/h3>\n<pre lang=\"haskell\">\nmodule TablaConMatrices \n    (Tabla,\n     tabla,     -- Eq i => [(i,v)] -> Tabla i v           \n     valor,     -- Eq i => Tabla i v -> i -> v            \n     modifica,  -- Eq i => (i,v) -> Tabla i v -> Tabla i v\n     tieneValor -- Ix i => Tabla i v -> i -> Bool\n    ) where\n\nimport Data.Array (Array, Ix, array, (\/\/), (!), bounds, inRange)\n\n-- Las tablas como matrices.\nnewtype Tabla i v = Tbl (Array i v)\n    deriving (Show, Eq)\n\n-- Ejemplos de tablas:\n--    ghci> t1\n--    Tbl (array (1,6) [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)])\n--    ghci> t2\n--    Tbl (array (1,3) [(1,5),(2,4),(3,7)])\nt1 = tabla [(i,f i) | i <- [1..6] ] \n     where f x | x < 3     = x\n               | otherwise = 3-x\nt2 = tabla [(1,5),(2,4),(3,7)]\n    \n-- (tabla ivs) es la tabla correspondiente a la lista de asociaci\u00f3n\n-- ivs (que es una lista de pares formados por los \u00edndices y los\n-- valores). Por ejemplo,\n--    ghci> tabla [(1,5),(3,7),(2,4)]\n--    Tbl (array (1,3) [(1,5),(2,4),(3,7)])\ntabla :: Ix i => [(i,v)] -> Tabla i v\ntabla ivs = Tbl (array (m,n) ivs)\n    where indices = [i | (i,_) <- ivs]\n          m       = minimum indices\n          n       = maximum indices\n\n-- (valor t i) es el valor del \u00edndice i en la tabla t. Por ejemplo, \n--    valor t1 6  ==  -3\n--    valor t2 2  ==   4\n--    valor t2 5  ==  *** Exception: Index (5) out of range ((1,3))\nvalor :: Ix i => Tabla i v -> i -> v\nvalor (Tbl t) i = t ! i\n\n-- (modifica (i,x) t) es la tabla obtenida modificando en la tabla t el\n-- valor de i por x. Por ejemplo, \n--    valor t1 6                   ==  -3\n--    valor (modifica (6,9) t1) 6  ==  9\nmodifica :: Ix i => (i,v) -> Tabla i v -> Tabla i v\nmodifica p (Tbl t) = Tbl (t \/\/ [p])\n\n-- (cotas t) son las cotas de la tabla t. Por ejemplo,\n--    t2        ==  Tbl (array (1,3) [(1,5),(2,4),(3,7)])\n--    cotas t2  ==  (1,3)\ncotas :: Ix i => Tabla i v -> (i,i)\ncotas (Tbl t) = bounds t\n\n-- (tieneValor t x) se verifica si x es una clave de la tabla t. Por ejemplo,\n--    tieneValor t2 3  ==  True\n--    tieneValor t2 4  ==  False\ntieneValor :: Ix i => Tabla i v -> i -> Bool\ntieneValor t = inRange (cotas t)\n<\/pre>\n<h3>Propiedades de las tablas<\/h3>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n\n-- Nota: Hay que elegir una implementaci\u00f3n del TAD tabla:\nimport TablaConListasDeAsociacion\n-- import TablaConMatrices (Pendiente de depurar)\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Generadores de tablas                                              --\n-- ---------------------------------------------------------------------\n\n-- genTabla es un generador de tablas. Por ejemplo,\n--    ghci> sample genTabla\n--    Tbl [(1,0)]\n--    Tbl [(1,-1)]\n--    Tbl [(1,0),(2,-1),(3,1),(4,1),(5,0)]\n--    Tbl [(1,1),(2,-1),(3,-1),(4,3)]\n--    Tbl [(1,3),(2,-5),(3,-7),(4,-2),(5,-8)]\n--    Tbl [(1,16),(2,-6),(3,-13),(4,-7),(5,2),(6,11)]\n--    Tbl [(1,-4),(2,-1),(3,3),(4,5)]\n--    Tbl [(1,-8),(2,16),(3,32)]\ngenTabla :: Gen (Tabla Int Int)\ngenTabla = \n    do x <- arbitrary\n       xs <- listOf arbitrary\n       return (tabla (zip [1..] (x:xs)))\n\n-- Las tablas son concreciones de los arbitrarios.\ninstance Arbitrary (Tabla Int Int) where\n    arbitrary = genTabla\n\n-- ---------------------------------------------------------------------\n-- Propiedades                                                        --\n-- ---------------------------------------------------------------------\n\n-- Propiedades de modifica\n-- -----------------------\n\n-- Propiedad. Al modificar una tabla dos veces con la misma clave se\n-- obtiene el mismos resultado que modificarla una vez con el \u00faltimo\n-- valor. \nprop_modifica_modifica_1 :: Int -> Int -> Int -> Tabla Int Int -> Bool\nprop_modifica_modifica_1 i v v1 t =\n    modifica (i,v1) (modifica (i,v) t) \n    == modifica (i,v1) t \n\n-- Comprobaci\u00f3n.\n--    ghci> quickCheck prop_modifica_modifica_1\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. Al modificar una tabla con dos pares con claves distintas\n-- no importa el orden en que se a\u00f1adan los pares. \nprop_modifica_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int \n                              -> Property\nprop_modifica_modifica_2 i i1 v v1 t =\n    i \/= i1 ==>\n    modifica (i1,v1) (modifica (i,v) t) \n    == modifica (i,v) (modifica (i1,v1) t) \n\n-- Comprobaci\u00f3n.\n--    ghci> quickCheck prop_modifica_modifica_2\n--    +++ OK, passed 100 tests.\n\n-- Propiedades de valor\n-- --------------------\n\n-- Propiedad. El valor de la clave i en la tabla obtenida a\u00f1adi\u00e9ndole el\n-- par (i,v) a la tabla t es v.\nprop_valor_modifica_1 :: Int -> Int -> Tabla Int Int -> Bool\nprop_valor_modifica_1 i v t =\n    valor (modifica (i,v) t) i == v\n\n-- Comprobaci\u00f3n.\n--    ghci> quickCheck prop_valor_modifica_1\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. Sean i y i1 dos claves distintas. El valor de la clave i1\n-- en la tabla obtenida a\u00f1adi\u00e9ndole el par (i,v) a la tabla t1 (que\n-- contiene la clave i1) es el valor de i1 en t1. \nprop_valor_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int \n                            -> Property\nprop_valor_modifica_2 i v i1 v1 t =\n    i \/= i1 ==>\n    valor (modifica (i,v) t1) i1 == valor t1 i1\n    where t1 = modifica (i1,v1) t\n\n-- Comprobaci\u00f3n.\n--    ghci> quickCheck prop_valor_modifica_2\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>Las transparencias usadas en la clase son las del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-18t.pdf\">tema 18<\/a>.<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 primera parte de la clase de hoy del curso de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se ha estudiado c\u00f3mo trabajar con tablas en Haskell usando el m\u00f3dulo Data.Array y en la segunda parte se ha estudiado el TAD (tipo abstracto de datos) de las tablas y tres implementaciones en Haskell: como&#8230;<\/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":[270,305,126],"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\/4700"}],"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=4700"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4700\/revisions"}],"predecessor-version":[{"id":4703,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4700\/revisions\/4703"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4700"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4700"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4700"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}