{"id":7668,"date":"2022-03-07T16:15:53","date_gmt":"2022-03-07T15:15:53","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7668"},"modified":"2022-03-07T16:15:53","modified_gmt":"2022-03-07T15:15:53","slug":"pfh-ejercicios-sobre-tablas-y-diccionarios-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-ejercicios-sobre-tablas-y-diccionarios-en-haskell\/","title":{"rendered":"PFH: Ejercicios sobre tablas y diccionarios en Haskell"},"content":{"rendered":"<p>He a\u00f1adido a la colecci\u00f3n de <a href=\"https:\/\/bit.ly\/3CeabJd\">Ejercicios de programaci\u00f3n funcional con Haskell<\/a> dos nuevas relaciones:<\/p>\n<ul>\n<li><a href=\"https:\/\/bit.ly\/3pIWBZh\">El tipo abstracto de las tablas<\/a> y<\/li>\n<li><a href=\"https:\/\/bit.ly\/3twws0K\">Correspondencia entre tablas y diccionarios<\/a>.<\/li>\n<\/ul>\n<p>En la <a href=\"#rel1\">primera<\/a>, se define el tipo abstracto de dato (TAD) de las tablas como lista de asociaci\u00f3n de claves y valores. Los procedimientos del TAD son<\/p>\n<pre lang=\"text\">\n   vacia         :: Tabla k v\n   inserta       :: k -> v -> Tabla k v -> Tabla k v\n   borra         :: Eq k => k -> Tabla k v -> Tabla k v\n   busca         :: Eq k => k -> Tabla k v -> Maybe v\n   aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2\n   aplicaClaves  :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v\n   ajusta        :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v\n<\/pre>\n<p>En la <a href=\"#rel2\">segunda<\/a>, se comprueba con QuickCheck c\u00f3mo las anteriores funciones de la tablas se corresponden con funciones de diccionarios de la libreria Data.Map.<\/p>\n<p>El contenido de las relaciones es el siguiente<br \/>\n<!--more--><br \/>\n<a name=\"rel1\"><\/a><\/p>\n<h3>El tipo abstracto de las tablas<\/h3>\n<pre lang=\"haskell\">\nmodule Tablas\n  ( Tabla (..)\n  , vacia, inserta, borra, busca, aplicaValores, aplicaClaves, ajusta\n  )\nwhere\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir el tipo (Tabla k v) de las tablas con claves de\n-- tipo k y valores de tipo v.\n-- ---------------------------------------------------------------------\n\nnewtype Tabla k v = Tabla [(k, v)]\n  deriving (Eq, Show)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    vacia :: Tabla k v\n-- tal que vacia es la tabla vac\u00eda.\n-- ---------------------------------------------------------------------\n\nvacia :: Tabla k v\nvacia = Tabla []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    inserta :: k -> v -> Tabla k v -> Tabla k v\n-- tal que\n--    inserta 2 'a' vacia                 == Tabla [(2,'a')]\n--    inserta 4 'd' (inserta 2 'a' vacia) == Tabla [(4,'d'),(2,'a')]\n-- ---------------------------------------------------------------------\n\ninserta :: k -> v -> Tabla k v -> Tabla k v\ninserta k v (Tabla kvs) = Tabla ((k, v) : kvs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    borra :: Eq k => k -> Tabla k v -> Tabla k v\n-- tal que (borra k t) es la tabla obtenida borrando los pares de t\n-- cuya clave es k. Por ejemplo,\n--    \u03bb> borra 2 (Tabla [(2,'a'),(3,'b'),(2,'a')])\n--    Tabla [(3,'b')]\n-- ---------------------------------------------------------------------\n\nborra :: Eq k => k -> Tabla k v -> Tabla k v\nborra k (Tabla kvs) = Tabla $ filter (\\(k', _) -> k' \/= k) kvs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    busca :: Eq k => k -> Tabla k v -> Maybe v\n-- tal que (busca k t) es el valor de la clave k en la tabla t. Por ejemplo,\n--    busca 2 (Tabla [(2,'a'),(3,'b'),(2,'d')])  ==  Just 'a'\n--    busca 4 (Tabla [(2,'a'),(3,'b'),(2,'d')])  ==  Nothing\n-- ---------------------------------------------------------------------\n\nbusca :: Eq k => k -> Tabla k v -> Maybe v\nbusca _ (Tabla [])              = Nothing\nbusca k (Tabla ((k', v) : kvs))\n  | k == k'                      = Just v\n  | otherwise                    = busca k (Tabla kvs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2\n-- tal que (aplicaValores f t) es la tabla obtenida aplicando la funci\u00f3n f a\n-- los valores de t. Por ejemplo,\n--    \u03bb> aplicaValores (+2) (Tabla [('a',5),('b',7),('c',4)])\n--    Tabla [('a',7),('b',9),('c',6)]\n-- ---------------------------------------------------------------------\n\naplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2\naplicaValores _ (Tabla [])             = vacia\naplicaValores f (Tabla ((k, v) : kvs)) = inserta k (f v) (aplicaValores f (Tabla kvs))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    aplicaClaves :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v\n-- tal que (aplicaClaves f t) es la tabla obtenida aplicando la funci\u00f3n f a\n-- las claves de t. Por ejemplo,\n--    \u03bb> aplicaClaves (+2) (Tabla [(2,'a'),(3,'b'),(2,'d')])\n--    Tabla [(4,'a'),(5,'b'),(4,'d')]\n-- ---------------------------------------------------------------------\n\naplicaClaves :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v\naplicaClaves _ (Tabla [])             = vacia\naplicaClaves f (Tabla ((k, v) : kvs)) = inserta (f k) v (aplicaClaves f (Tabla kvs))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    ajusta :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v\n-- tal que (ajusta f k t) es el ajuste de la tabla t de acuerdo a las\n-- siguientes reglas:\n-- + Si `f k` es `Nothing` y `k` es una clave de t, borra el par con\n--   clave `k`.\n-- + Si `f k` es `Nothing` y `k` no es una clave de t, no hace nada.\n-- + Si `f k` es `Just v` y `k` es una clave de t, cambia el valor de\n--   `k` a `v`.\n-- + Si `f k` es `Just v` y `k` no es una clave de t, a\u00f1ade el par `(h, v)`.\n-- Por ejemplo,\n--    \u03bb> ajusta (\\_ -> Nothing) 4 (Tabla [(3,2),(4,5)])\n--    Tabla [(3,2)]\n--    \u03bb> ajusta (\\_ -> Nothing) 7 (Tabla [(3,2),(4,5)])\n--    Tabla [(3,2),(4,5)]\n--    \u03bb> ajusta (\\_ -> Just 9) 4 (Tabla [(3,2),(4,5)])\n--    Tabla [(3,2),(4,9)]\n--    \u03bb> ajusta (\\_ -> Just 9) 7 (Tabla [(3,2),(4,5)])\n--    Tabla [(3,2),(4,5),(7,9)]\n--    \u03bb> ajusta ((+ 2) <$>) 4 (Tabla [(3,2),(4,5)])\n--    Tabla [(3,2),(4,7)]\n--    \u03bb> ajusta ((+ 2) <$>) 7 (Tabla [(3,2),(4,5)])\n--    Tabla [(3,2),(4,5)]\n--    \u03bb> ajusta (\\_ -> Nothing) 3 (Tabla [])\n--    Tabla []\n--    \u03bb> ajusta (\\_ -> Just 7) 3 (Tabla [])\n--    Tabla [(3,7)]\n--    \u03bb> ajusta (\\_ -> Nothing) 3 (Tabla [(3,1),(2,5),(3,7),(4,3)])\n--    Tabla [(2,5),(4,3)]\n--    \u03bb> ajusta ((+ 2) <$>) 3 (Tabla [(3,1),(2,5),(3,7),(4,3)])\n--    Tabla [(3,3),(2,5),(3,7),(4,3)]\n--    \u03bb> ajusta (\\_ -> Nothing) 3 (Tabla [(2,5),(3,7),(4,3)])\n--    Tabla [(2,5),(4,3)]\n--    \u03bb> ajusta ((+ 2) <$>) 3 (Tabla [(2,5),(3,7),(4,3)])\n--    Tabla [(2,5),(3,9),(4,3)]\n-- ---------------------------------------------------------------------\n\najusta :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v\najusta f k (Tabla []) =\n  case f Nothing of\n    Nothing -> Tabla []\n    Just v  -> Tabla [(k, v)]\najusta f k (Tabla ((k', v) : kvs))\n  | k == k' =\n      case f (Just v) of\n        Nothing -> Tabla $ filter (\\(k'', _) -> k'' \/= k) kvs\n        Just v' -> Tabla $ (k, v') : kvs\n  | otherwise =\n      case ajusta f k (Tabla kvs) of\n        Tabla kvs' -> Tabla $ (k', v) : kvs'\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Referencias                                                      --\n-- ---------------------------------------------------------------------\n\n-- Esta relaci\u00f3n de ejercicio es una adaptaci\u00f3n de\n-- \"Tables.hs\" https:\/\/bit.ly\/3Cli8vV de Lars Br\u00fcnjes.\n<\/pre>\n<p><a name=\"rel2\"><\/a><\/p>\n<h3>Correspondencia entre tablas y diccionarios<\/h3>\n<pre lang=\"haskell\">\nmodule Tablas_y_diccionarios where\n\nimport Prelude hiding (lookup)\nimport Tablas\nimport Data.Map.Strict (Map, empty, insert, delete, lookup, mapKeys, alter)\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    tablaAdiccionario :: Ord k => Tabla k v -> Map k v\n-- tal que (tablaAdiccionario t) es el diccionario correspondiente a la\n-- tabla t. Por ejemplo,\n--    \u03bb> tablaAdiccionario (inserta 4 'd' (inserta 2 'a' vacia))\n--    fromList [(2,'a'),(4,'d')]\n-- ---------------------------------------------------------------------\n\ntablaAdiccionario :: Ord k => Tabla k v -> Map k v\ntablaAdiccionario (Tabla xs) =\n  foldr (uncurry insert) empty xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir el procedimiento\n--    tablaArbitraria :: (Arbitrary k, Arbitrary v) => Gen (Tabla k v)\n-- tal que tablaArbitraria es una tabla aleatoria. Por ejemplo,\n--    \u03bb> sample (tablaArbitraria :: Gen (Tabla Int Int))\n--    Tabla []\n--    Tabla [(-3,3),(-2,-4)]\n--    Tabla [(5,-2),(3,-9),(6,10),(-2,-1),(10,0),(3,8),(-10,-1),(5,-10),(-7,-1)]\n--    Tabla [(-11,-4),(2,2),(6,-2),(11,-3),(-1,-3)]\n--    Tabla [(16,7),(15,8),(-6,2),(13,14),(15,2),(4,-10),(17,15),(12,4),(-17,-2)]\n--    ...\n-- ---------------------------------------------------------------------\n\ntablaArbitraria :: (Arbitrary k, Arbitrary v) => Gen (Tabla k v)\ntablaArbitraria = Tabla <$> arbitrary\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Declarar Tabla como subclase de Arbitraria usando el\n-- generador tablaArbitraria.\n-- ---------------------------------------------------------------------\n\ninstance (Arbitrary k, Arbitrary v) => Arbitrary (Tabla k v) where\n  arbitrary = tablaArbitraria\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Comprobar con QuickCheck que la funci\u00f3n `inserta` es\n-- equivalente a la funci\u00f3n `insert` de Data.Map.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_inserta :: Int -> Int -> Tabla Int Int -> Property\nprop_inserta n c t =\n  tablaAdiccionario (inserta n c t) === insert n c (tablaAdiccionario t)\n\n-- la comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_inserta\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Comprobar con QuickCheck que la funci\u00f3n `borra`es\n-- equivalente a la funci\u00f3n `delete` de Data.Map.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_borra :: Int -> Tabla Int Char -> Property\nprop_borra n t =\n  tablaAdiccionario (borra n t) === delete n (tablaAdiccionario t)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_borra\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Comprobar con QuickCheck que la funci\u00f3n `busca`es\n-- equivalente a la funci\u00f3n `lookup` de Data.Map.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_busca :: Int -> Tabla Int Bool -> Property\nprop_busca n t =\n  busca n t === lookup n (tablaAdiccionario t)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_busca\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Comprobar con QuickCheck que la funci\u00f3n `aplicaValores`\n-- es compatible con la `fmap` de Data.Map.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_aplicaValores :: Fun Char Bool -> Tabla Int Char -> Property\nprop_aplicaValores f t =\n  tablaAdiccionario (aplicaValores (applyFun f) t)\n  === (applyFun f <$> tablaAdiccionario t)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_aplicaValores\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Comprobar con QuickCheck que la funci\u00f3n `aplicaClaves`\n-- es compatible con la `mapKeys` de Data.Map.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_aplicaClaves :: Tabla Int Char -> Property\nprop_aplicaClaves t =\n  tablaAdiccionario (aplicaClaves succ t)\n  === mapKeys succ (tablaAdiccionario t)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_aplicaClaves\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Comprobar con QuickCheck que la funci\u00f3n `ajusta`\n-- es equivalente a la `alter` de Data.Map.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_ajusta :: Fun (Maybe Char) (Maybe Char) -> Int -> Tabla Int Char -> Property\nprop_ajusta f n t =\n  tablaAdiccionario (ajusta (applyFun f) n t)\n  === alter (applyFun f) n (tablaAdiccionario t)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ajusta\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>He a\u00f1adido a la colecci\u00f3n de Ejercicios de programaci\u00f3n funcional con Haskell dos nuevas relaciones: El tipo abstracto de las tablas y Correspondencia entre tablas y diccionarios. En la primera, se define el tipo abstracto de dato (TAD) de las tablas como lista de asociaci\u00f3n de claves y valores. Los procedimientos del TAD son vacia&#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":[337],"tags":[],"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\/7668"}],"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=7668"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7668\/revisions"}],"predecessor-version":[{"id":7669,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7668\/revisions\/7669"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7668"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}