{"id":1909,"date":"2012-02-22T17:11:57","date_gmt":"2012-02-22T17:11:57","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1909"},"modified":"2013-03-08T05:48:55","modified_gmt":"2013-03-08T05:48:55","slug":"i1m2011-ejercicios-sobre-tipos-algebraicos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-ejercicios-sobre-tipos-algebraicos-en-haskell\/","title":{"rendered":"I1M2011: Ejercicios sobre tipos algebraicos 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 han explicado las soluciones de los ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_18.hs\">18\u00aa relaci\u00f3n<\/a>. <\/p>\n<p>En esta relaci\u00f3n se presenta ejercicios sobre tipos de datos algebraicos. Se consideran dos tipos de datos algebraicos: los n\u00fameros naturales (para los que se define su producto) y los \u00e1rboles binarios, para los que se definen funciones para calcular:<\/p>\n<ul>\n<li> la ocurrencia de un elemento en el \u00e1rbol,\n<li> el n\u00famero de hojas\n<li> el car\u00e1cter balanceado de un \u00e1rbol,\n<li> el \u00e1rbol balanceado correspondiente a una lista,\n<\/ul>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Usando el tipo de dato Nat y la funci\u00f3n suma definidas\r\n-- en las transparencias del tema 9, definir la funci\u00f3n\r\n--    producto :: Nat -> Nat -> Nat\r\n-- tal que (producto m n) es el producto de los n\u00fameros naturales m y\r\n-- n. Por ejemplo, \r\n--    ghci> producto (Suc (Suc Cero)) (Suc (Suc (Suc Cero)))\r\n--    Suc (Suc (Suc (Suc (Suc (Suc Cero)))))\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Nat = Cero | Suc Nat\r\n           deriving (Eq, Show)\r\n\r\nsuma :: Nat -> Nat -> Nat\r\nsuma Cero    n = n\r\nsuma (Suc m) n = Suc (suma m n)\r\n\r\nproducto :: Nat -> Nat -> Nat\r\nproducto Cero _    = Cero\r\nproducto (Suc m) n = suma n (producto m n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Nota. En los siguientes ejercicios se trabajar\u00e1 con \u00e1rboles binarios\r\n-- definidos como sigue\r\n--    data Arbol = Hoja Int \r\n--               | Nodo Arbol Int Arbol\r\n--               deriving (Show, Eq)\r\n-- Por ejemplo, el \u00e1rbol\r\n--         5 \r\n--        \/ \\\r\n--       \/   \\\r\n--      3     7\r\n--     \/ \\   \/ \\  \r\n--    1   4 6   9  \r\n-- se representa por\r\n--    Nodo (Nodo (Hoja 1) 3 (Hoja 4)) \r\n--         5 \r\n--         (Nodo (Hoja 6) 7 (Hoja 9))\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Arbol = Hoja Int \r\n           | Nodo Arbol Int Arbol\r\n           deriving (Show, Eq)\r\n\r\nejArbol :: Arbol\r\nejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4)) \r\n               5 \r\n               (Nodo (Hoja 6) 7 (Hoja 9))\r\n\r\n-- --------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    ocurre :: Int -> Arbol -> Bool\r\n-- tal que (ocurre x a) se verifica si x ocurre en el \u00e1rbol a como valor\r\n-- de un nodo o de una hoja. Por ejemplo,\r\n--    ocurre  4 ejArbol  ==  True\r\n--    ocurre 10 ejArbol  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nocurre :: Int -> Arbol -> Bool\r\nocurre m (Hoja n)     = m == n\r\nocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. En el preludio est\u00e1 definido el tipo de datos\r\n--    data Ordering = LT | EQ | GT\r\n-- junto con la funci\u00f3n\r\n--    compare :: Ord a => a -> a -> Ordering\r\n-- que decide si un valor en un tipo ordenado es menor (LT), igual (EQ)\r\n-- o mayor (GT) que otro. \r\n-- \r\n-- Usando esta funci\u00f3n, redefinir la funci\u00f3n\r\n--    ocurre :: Int -> Arbol -> Bool\r\n-- del ejercicio anterior. \r\n-- ---------------------------------------------------------------------\r\n\r\nocurre' :: Int -> Arbol -> Bool\r\nocurre' m (Hoja n)     = m == n\r\nocurre' m (Nodo i n d) = case compare m n of\r\n                           LT -> ocurre' m i\r\n                           EQ -> True\r\n                           GT -> ocurre' m d\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. \u00bfPorqu\u00e9 la segunda definici\u00f3n de ocurre es m\u00e1s eficiente\r\n-- que la primera? \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La nueva definici\u00f3n es m\u00e1s eficiente porque s\u00f3lo necesita una\r\n-- comparaci\u00f3n por nodo, mientras que la definici\u00f3n de las\r\n-- transparencias necesita dos comparaciones por nodo.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Nota. En los siguientes ejercicios se trabajar\u00e1 con \u00e1rboles binarios\r\n-- definidos como sigue\r\n--    type ArbolB = HojaB Int \r\n--                | NodoB ArbolB ArbolB \r\n--                deriving Show\r\n-- Por ejemplo, el \u00e1rbol\r\n--         . \r\n--        \/ \\\r\n--       \/   \\\r\n--      .     .\r\n--     \/ \\   \/ \\  \r\n--    1   4 6   9  \r\n-- se representa por\r\n--    NodoB (NodoB (HojaB 1) (HojaB 4)) \r\n--          (NodoB (HojaB 6) (HojaB 9))\r\n-- ---------------------------------------------------------------------\r\n\r\ndata ArbolB = HojaB Int \r\n            | NodoB ArbolB ArbolB\r\n            deriving Show\r\n\r\nejArbolB :: ArbolB\r\nejArbolB = NodoB (NodoB (HojaB 1) (HojaB 4)) \r\n                 (NodoB (HojaB 6) (HojaB 9))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n \r\n--    nHojas :: ArbolB -> Int\r\n-- tal que (nHojas a) es el n\u00famero de hojas del \u00e1rbol a. Por ejemplo,\r\n--    nHojas (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7)))  ==  3\r\n--    nHojas ejArbolB ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nnHojas :: ArbolB -> Int\r\nnHojas (HojaB _)     = 1\r\nnHojas (NodoB a1 a2) = nHojas a1 + nHojas a2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Se dice que un \u00e1rbol de este tipo es balanceado si es\r\n-- una hoja o bien si para cada nodo se tiene que el n\u00famero de hojas en\r\n-- cada uno de sus sub\u00e1rboles difiere como m\u00e1ximo en uno y sus\r\n-- sub\u00e1rboles son balanceados. Definir la funci\u00f3n \r\n--    balanceado :: ArbolB -> BoolB\r\n-- tal que (balanceado a) se verifica si a es un \u00e1rbol balanceado. Por\r\n-- ejemplo, \r\n--    balanceado ejArbolB\r\n--    ==> True\r\n--    balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7)))\r\n--    ==> True\r\n--    balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (NodoB (HojaB 5) (HojaB 7))))\r\n--    ==> False\r\n-- ---------------------------------------------------------------------\r\n \r\nbalanceado :: ArbolB -> Bool\r\nbalanceado (HojaB _)     = True\r\nbalanceado (NodoB a1 a2) = abs (nHojas a1 - nHojas a2) <= 1 &#038;&#038;\r\n                           balanceado a1 &#038;&#038;\r\n                           balanceado a2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n \r\n--    mitades :: [a] -> ([a],[a]) \r\n-- tal que (mitades xs) es un par de listas que se obtiene al dividir xs\r\n-- en dos mitades cuya longitud difiere como m\u00e1ximo en uno. Por ejemplo,\r\n--    mitades [2,3,5,1,4,7]    ==  ([2,3,5],[1,4,7])\r\n--    mitades [2,3,5,1,4,7,9]  ==  ([2,3,5],[1,4,7,9])\r\n-- ---------------------------------------------------------------------\r\n\r\nmitades :: [a] -> ([a],[a])\r\nmitades xs = splitAt (length xs `div` 2) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    arbolBalanceado :: [Int] -> ArbolB\r\n-- tal que (arbolBalanceado xs) es el \u00e1rbol balanceado correspondiente\r\n-- a la lista xs. Por ejemplo,\r\n--    ghci> arbolBalanceado [2,5,3]\r\n--    NodoB (HojaB 2) (NodoB (HojaB 5) (HojaB 3))\r\n--    ghci> arbolBalanceado [2,5,3,7]\r\n--    NodoB (NodoB (HojaB 2) (HojaB 5)) (NodoB (HojaB 3) (HojaB 7))\r\n-- ---------------------------------------------------------------------\r\n\r\narbolBalanceado :: [Int] -> ArbolB\r\narbolBalanceado [x] = HojaB x\r\narbolBalanceado xs  = NodoB (arbolBalanceado ys) (arbolBalanceado zs)\r\n                      where (ys,zs) = mitades xs\r\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 han explicado las soluciones de los ejercicios de la 18\u00aa relaci\u00f3n. En esta relaci\u00f3n se presenta ejercicios sobre tipos de datos algebraicos. Se consideran dos tipos de datos algebraicos: los n\u00fameros naturales (para los que se define su producto) y los&#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\/1909"}],"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=1909"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1909\/revisions"}],"predecessor-version":[{"id":2847,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1909\/revisions\/2847"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1909"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1909"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1909"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}