{"id":6626,"date":"2019-04-05T20:04:33","date_gmt":"2019-04-05T18:04:33","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6626"},"modified":"2019-04-05T20:04:33","modified_gmt":"2019-04-05T18:04:33","slug":"i1m2018-ejercicios-con-el-tipo-abstracto-de-dato-de-los-monticulos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-ejercicios-con-el-tipo-abstracto-de-dato-de-los-monticulos\/","title":{"rendered":"I1M2018: Ejercicios con el tipo abstracto de dato de los mont\u00edculos"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han resuelto ejercicios de la relaci\u00f3n 32 sobre el tipo de datos abstracto de los mont\u00edculos.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n de ejercicios es definir funciones sobre \n-- el TAD de las mont\u00edculos, utilizando las implementaciones estudiadas\n-- en el tema 20 que se encuenta en\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\/temas\/tema-20.html\n-- \n-- Para realizar los ejercicios hay que tener instalada la librer\u00eda I1M\n-- que contiene la implementaci\u00f3n de TAD de los mont\u00edculos. Los pasos\n-- para instalarla son los siguientes:\n-- + Descargar el paquete I1M desde http:\/\/bit.ly\/1pbnDqm\n-- + Descomprimirlo (y se crea el directorio I1M-master.zip).\n-- + Cambiar al directorio I1M-master.\n-- + Ejecutar cabal install I1M.cabal\n-- \n-- Otra forma es descargar la implementaci\u00f3n del TAD de mont\u00edculos:\n-- + Monticulo.hs que est\u00e1 en http:\/\/bit.ly\/1oNy2HT\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\n{-# LANGUAGE FlexibleInstances #-}\n\nimport Test.QuickCheck\n\n-- Hay que elegir una implementaci\u00f3n del TAD mont\u00edculos:\n-- import Monticulo\nimport I1M.Monticulo \n\n-- ---------------------------------------------------------------------\n-- Ejemplos                                                           --\n-- ---------------------------------------------------------------------\n\n-- Para los ejemplos se usar\u00e1n los siguientes mont\u00edculos.\nm1, m2, m3 :: Monticulo Int\nm1 = foldr inserta vacio [6,1,4,8]\nm2 = foldr inserta vacio [7,5]\nm3 = foldr inserta vacio [6,1,4,8,7,5]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    numeroDeNodos :: Ord a => Monticulo a -> Int\n-- tal que (numeroDeNodos m) es el n\u00famero de nodos del mont\u00edculo m. Por\n-- ejemplo, \n--    numeroDeNodos m1  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroDeNodos :: Ord a => Monticulo a -> Int\nnumeroDeNodos m\n  | esVacio m = 0\n  | otherwise = 1 + numeroDeNodos (resto m)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    filtra :: Ord a => (a -> Bool) -> Monticulo a -> Monticulo a\n-- tal que (filtra p m) es el mont\u00edculo con los nodos del mont\u00edculo m\n-- que cumplen la propiedad p. Por ejemplo,\n--    ghci> m1\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\n--    ghci> filtra even m1\n--    M 4 1 (M 6 1 (M 8 1 Vacio Vacio) Vacio) Vacio\n--    ghci> filtra odd m1\n--    M 1 1 Vacio Vacio\n-- ---------------------------------------------------------------------\n\nfiltra :: Ord a => (a -> Bool) -> Monticulo a -> Monticulo a\nfiltra p m\n  | esVacio m = vacio\n  | p mm      = inserta mm (filtra p rm)\n  | otherwise = filtra p rm\n  where mm = menor m\n        rm = resto m\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    menores :: Ord a => Int -> Monticulo a -> [a]\n-- tal que (menores n m) es la lista de los n menores elementos del\n-- mont\u00edculo m. Por ejemplo,\n--    ghci> m1\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\n--    ghci> menores 3 m1\n--    [1,4,6]\n--    ghci> menores 10 m1\n--    [1,4,6,8]\n-- ---------------------------------------------------------------------\n\nmenores :: Ord a => Int -> Monticulo a -> [a]\nmenores 0 _  = []\nmenores n m | esVacio m = []\n            | otherwise = menor m : menores (n-1) (resto m)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    restantes :: Ord a => Int -> Monticulo a -> Monticulo a\n-- tal que (restantes n m) es el mont\u00edculo obtenido eliminando los n\n-- menores elementos del mont\u00edculo m. Por ejemplo,\n--    ghci> m1\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\n--    ghci> restantes 3 m1\n--    M 8 1 Vacio Vacio\n--    ghci> restantes 2 m1\n--    M 6 1 (M 8 1 Vacio Vacio) Vacio\n--    ghci> restantes 7 m1\n--    Vacio\n-- ---------------------------------------------------------------------\n\nrestantes :: Ord a => Int -> Monticulo a -> Monticulo a\nrestantes 0 m  = m\nrestantes n m | esVacio m = vacio\n              | otherwise = restantes (n-1) (resto m)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    lista2Monticulo :: Ord a => [a] -> Monticulo a\n-- tal que (lista2Monticulo xs) es el mont\u00edculo cuyos nodos son los\n-- elementos de la lista xs. Por ejemplo,\n--    ghci> lista2Monticulo [2,5,3,7]\n--    M 2 1 (M 3 2 (M 7 1 Vacio Vacio) (M 5 1 Vacio Vacio)) Vacio\n-- ---------------------------------------------------------------------\n\nlista2Monticulo :: Ord a => [a] -> Monticulo a\nlista2Monticulo = foldr inserta vacio\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    monticulo2Lista :: Ord a => Monticulo a -> [a]\n-- tal que (monticulo2Lista m) es la lista ordenada de los nodos del\n-- mont\u00edculo m. Por ejemplo,\n--    ghci> m1\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\n--    ghci> monticulo2Lista m1\n--    [1,4,6,8]\n-- ---------------------------------------------------------------------\n\nmonticulo2Lista :: Ord a => Monticulo a -> [a]\nmonticulo2Lista m\n  | esVacio m = []\n  | otherwise = menor m : monticulo2Lista (resto m)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    ordenada :: Ord a => [a] -> Bool\n-- tal que (ordenada xs) se verifica si xs es una lista ordenada de\n-- forma creciente. Por ejemplo,\n--    ordenada [3,5,9]  ==  True\n--    ordenada [3,5,4]  ==  False\n--    ordenada [7,5,4]  ==  False\n-- ---------------------------------------------------------------------\n\nordenada :: Ord a => [a] -> Bool\nordenada (x:y:zs) = x <= y &#038;&#038; ordenada (y:zs)\nordenada _        = True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Comprobar con QuickCheck que para todo mont\u00edculo m,\n-- (monticulo2Lista m) es una lista ordenada creciente.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_monticulo2Lista_ordenada :: Monticulo Int -> Bool\nprop_monticulo2Lista_ordenada m =\n  ordenada (monticulo2Lista m)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_monticulo2Lista_ordenada\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Usando monticulo2Lista y lista2Monticulo, definir la\n-- funci\u00f3n \n--    ordena :: Ord a => [a] -> [a]\n-- tal que (ordena xs) es la lista obtenida ordenando de forma creciente\n-- los elementos de xs. Por ejemplo,\n--    ordena [7,5,3,6,5]  ==  [3,5,5,6,7]\n-- ---------------------------------------------------------------------\n\nordena :: Ord a => [a] -> [a]\nordena  = monticulo2Lista . lista2Monticulo\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Comprobar con QuickCheck que para toda lista xs,\n-- (ordena xs) es una lista ordenada creciente.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_ordena_ordenada :: [Int] -> Bool\nprop_ordena_ordenada xs =\n    ordenada (ordena xs)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ordena_ordenada\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    borra :: Eq a => a -> [a] -> [a]\n-- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de\n-- x en la lista xs. Por ejemplo, \n--    borra 1 [1,2,1]  ==  [2,1]\n--    borra 3 [1,2,1]  ==  [1,2,1]\n-- ---------------------------------------------------------------------\n\nborra :: Eq a => a -> [a] -> [a]\nborra _ []                 = []\nborra x (y:ys) | x == y    = ys\n               | otherwise = y : borra x ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n esPermutaci\u00f3n tal que \n-- (esPermutaci\u00f3n xs ys) se verifique si xs es una permutaci\u00f3n de\n-- ys. Por ejemplo,  \n--    esPermutaci\u00f3n [1,2,1] [2,1,1]  ==  True\n--    esPermutaci\u00f3n [1,2,1] [1,2,2]  ==  False\n-- ---------------------------------------------------------------------\n\nesPermutacion :: Eq a => [a] -> [a] -> Bool\nesPermutacion []     []    = True\nesPermutacion []     (_:_) = False\nesPermutacion (x:xs) ys    = elem x ys && esPermutacion xs (borra x ys)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Comprobar con QuickCheck que para toda lista xs,\n-- (ordena xs) es una permutaci\u00f3n de xs.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_ordena_permutacion :: [Int] -> Bool\nprop_ordena_permutacion xs =\n  esPermutacion (ordena xs) xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ordena_permutacion\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Generador de mont\u00edculos                                            --\n-- ---------------------------------------------------------------------\n\n-- genMonticulo es un generador de mont\u00edculos. Por ejemplo,\n--    ghci> sample genMonticulo\n--    VacioM\n--    M (-1) 1 (M 1 1 VacioM VacioM) VacioM\n--    ...\ngenMonticulo :: Gen (Monticulo Int)\ngenMonticulo = do xs <- listOf arbitrary\n                  return (foldr inserta vacio xs)\n\n-- Mont\u00edculo es una instancia de la clase arbitraria.\ninstance Arbitrary (Monticulo Int) where\n  arbitrary = genMonticulo\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han resuelto ejercicios de la relaci\u00f3n 32 sobre el tipo de datos abstracto de los mont\u00edculos. Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/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":[320],"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\/6626"}],"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=6626"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6626\/revisions"}],"predecessor-version":[{"id":6627,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6626\/revisions\/6627"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}