{"id":1846,"date":"2012-01-18T14:25:55","date_gmt":"2012-01-18T14:25:55","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1846"},"modified":"2013-03-08T05:48:56","modified_gmt":"2013-03-08T05:48:56","slug":"i1m2011-resolucion-de-problemas-matematicos-con-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-resolucion-de-problemas-matematicos-con-haskell-2\/","title":{"rendered":"I1M2011: Resoluci\u00f3n de problemas matem\u00e1ticos con Haskell (2)"},"content":{"rendered":"<p>En la primera parte de 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 5 \u00faltimos ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_12.hs\">12\u00aa relaci\u00f3n<\/a> en  la que se plantea la resoluci\u00f3n de distintos problemas<br \/>\nmatem\u00e1ticos. En concreto,<\/p>\n<ul>\n<li> el producto, por plegado, de los n\u00fameros que verifican una propiedad,\n<li> el car\u00e1cter funcional de una relaci\u00f3n,\n<li> las cabezas y las colas de una lista y\n<li> la identidad de Bezout.\n<\/ul>\n<p>Estos ejercicios corresponden a los temas <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-5.pdf\">5<\/a>, <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-6.pdf\">6<\/a> y <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-7.pdf\">7<\/a>.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- -------------------------------------------------------------------\r\n-- Ejercicio 7.1. Definir mediante plegado la funci\u00f3n \r\n--    producto :: Num a => [a] -> a\r\n-- tal que (producto xs) es el producto de los elementos de la lista\r\n-- xs. Por ejemplo, \r\n--    producto [2,1,-3,4,5,-6] == 720\r\n-- ---------------------------------------------------------------------\r\n\r\nproducto :: Num a => [a] -> a\r\nproducto = foldr (*) 1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.2. Definir mediante plegado la funci\u00f3n \r\n--    productoPred :: Num a => (a -> Bool) -> [a] -> a\r\n-- tal que (productoPred p xs) es el producto de los elementos de la\r\n-- lista xs que verifican el predicado p. Por ejemplo, \r\n--    productoPred even [2,1,-3,4,-5,6] == 48\r\n-- ---------------------------------------------------------------------\r\n\r\nproductoPred :: Num a => (a -> Bool) -> [a] -> a\r\nproductoPred p = foldr (\\x y -> if p x then x*y else y) 1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.3. Definir la funci\u00f3n \r\n--    productoPos :: (Num a, Ord a) => [a] -> a\r\n-- tal que (productoPos xs) esel producto de los elementos estr\u00edctamente\r\n-- positivos de la lista xs. Por ejemplo,\r\n--    productoPos [2,1,-3,4,-5,6] == 48\r\n-- ---------------------------------------------------------------------\r\n\r\nproductoPos :: (Num a, Ord a) => [a] -> a\r\nproductoPos = productoPred (>0)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Las relaciones finitas se pueden representar mediante\r\n-- listas de pares. Por ejemplo,\r\n--    r1, r2, r3 :: [(Int, Int)]\r\n--    r1 = [(1,3), (2,6), (8,9), (2,7)]\r\n--    r2 = [(1,3), (2,6), (8,9), (3,7)]\r\n--    r3 = [(1,3), (2,6), (8,9), (3,6)]\r\n-- Definir la funci\u00f3n \r\n--    esFuncion :: (Eq a, Eq b) => [(a,b)] -> Bool\r\n-- tal que (esFuncion r) se verifica si la relaci\u00f3n r es una funci\u00f3n (es\r\n-- decir, a cada elemento del dominio de la relaci\u00f3n r le corresponde un\r\n-- \u00fanico elemento). Por ejemplo, \r\n--    esFuncion r1 == False\r\n--    esFuncion r2 == True\r\n--    esFuncion r3 == True\r\n-- ---------------------------------------------------------------------\r\n\r\nr1, r2, r3 :: [(Int, Int)]\r\nr1 = [(1,3), (2,6), (8,9), (2,7)]\r\nr2 = [(1,3), (2,6), (8,9), (3,7)]\r\nr3 = [(1,3), (2,6), (8,9), (3,6)]\r\n\r\nesFuncion :: (Eq a, Eq b) => [(a,b)] -> Bool\r\nesFuncion [] = True\r\nesFuncion ((x,y):r) = \r\n    [y' | (x',y') <- r, x == x', y \/= y'] == [] &#038;&#038; esFuncion r \r\n\r\n-- -------------------------------------------------------------------\r\n-- Ejercicio 9.1. Se denomina cola de una lista l a una sublista no\r\n-- vac\u00eda de l formada por un elemento y los siguientes hasta el\r\n-- final. Por ejemplo, [3,4,5] es una cola de la lista [1,2,3,4,5]. \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    colas :: [a] -> [[a]]\r\n-- tal que (colas xs) es la lista de las colas\r\n-- de la lista xs. Por ejemplo, \r\n--    colas []        == [[]]\r\n--    colas [1,2]     == [[1,2],[2],[]]\r\n--    colas [4,1,2,5] == [[4,1,2,5],[1,2,5],[2,5],[5],[]]\r\n-- ---------------------------------------------------------------------\r\n\r\ncolas :: [a] -> [[a]]\r\ncolas []     = [[]]\r\ncolas (x:xs) = (x:xs) : colas xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9.2. Comprobar con QuickCheck que las funciones colas y\r\n-- tails son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_colas :: [Int] -> Bool\r\nprop_colas xs = colas xs == tails xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_colas\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10.1. Se denomina cabeza de una lista l a una sublista no\r\n-- vac\u00eda de la formada por el primer elemento y los siguientes hasta uno\r\n-- dado. Por ejemplo, [1,2,3] es una cabeza de [1,2,3,4,5]. \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    cabezas :: [a] -> [[a]]\r\n-- tal que (cabezas xs) es la lista de las cabezas de la lista xs. Por\r\n-- ejemplo, \r\n--    cabezas []          == [[]] \r\n--    cabezas [1,4]       == [[],[1],[1,4]] \r\n--    cabezas [1,4,5,2,3] == [[],[1],[1,4],[1,4,5],[1,4,5,2],[1,4,5,2,3]] \r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1. Por recursi\u00f3n\r\ncabezas :: [a] -> [[a]]\r\ncabezas []     = [[]]\r\ncabezas (x:xs) = [] : [x:ys | ys <- cabezas xs]\r\n\r\n-- 2. Usando patrones de plegado.\r\ncabezasP :: [a] -> [[a]]\r\ncabezasP = foldr (\\x y -> [x]:[x:ys | ys <- y]) []\r\n\r\n-- 3. Usando colas y funciones de orden superior.\r\ncabezas3 :: [a] -> [[a]]\r\ncabezas3 xs = reverse (map reverse (colas (reverse xs)))\r\n\r\n-- La anterior definici\u00f3n puede escribirse sin argumentos como \r\ncabezas3' :: [a] -> [[a]]\r\ncabezas3' = reverse . map reverse . (colas . reverse)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10.2. Comprobar con QuickCheck que las funciones cabezas y\r\n-- inits son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_cabezas :: [Int] -> Bool\r\nprop_cabezas xs = cabezas xs == inits xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_cabezas\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11.1. [La identidad de Bezout] Definir la funci\u00f3n\r\n--    bezout :: Integer -> Integer -> (Integer, Integer)\r\n-- tal que (bezout a b) es un par de n\u00fameros x e y tal que a*x+b*y es el\r\n-- m\u00e1ximo com\u00fan divisor de a y b. Por ejemplo,\r\n--    bezout 21 15  ==  (-2,3)\r\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n quotRem tal que (quotRem x y) es\r\n-- el par formado por el cociente y el resto de dividir x entre y.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Ejemplo de c\u00e1lculo\r\n--    a  b   q r   \r\n--    36 21  1 15   (1)\r\n--    21 15  1  6   (2) \r\n--    15  6  2  3   (3)\r\n--     6  3  2  0\r\n--     3  0   \r\n-- Por tanto,\r\n--    3 = 15 - 6*2              [por (3)]\r\n--      = 15 - (21-15*1)*2      [por (2)]\r\n--      = 21*(-2) + 15*3        \r\n--      = 21*(-2)+ (36-21*1)*3  [por (1)]\r\n--      = 36*3 + 21*(-5)\r\n\r\n-- Sean q, r el cociente y el resto de a entre b, d el m\u00e1ximo com\u00fan\r\n-- denominador de a y b y (x,y) el valor de (bezout b r) . Entonces,\r\n--    a = bp+r\r\n--    d = bx+ry\r\n-- Por tanto,\r\n--    d = bx + (a-bp)y\r\n--      = ay + b(x-qy)\r\n-- Luego,\r\n--    bezout a b = (y,x-qy)\r\n\r\nbezout :: Integer -> Integer -> (Integer, Integer)\r\nbezout _ 0 = (1,0)\r\nbezout _ 1 = (0,1)\r\nbezout a b = (y, x-q*y)\r\n    where (x,y) = bezout b r\r\n          (q,r) = quotRem a b\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11.2. Comprobar con QuickCheck que si a>0, b>0 y \r\n-- (x,y) es el valor de (bezout a b), entonces a*x+b*y es igual al\r\n-- m\u00e1ximo com\u00fan divisor de a y b.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_Bezout :: Integer -> Integer -> Property\r\nprop_Bezout a b = a>0 && b>0 ==> a*x+b*y == gcd a b\r\n    where (x,y) = bezout a b          \r\n\r\n-- La comprobaci\u00f3n es\r\n--   Main> quickCheck prop_Bezout\r\n--   OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los 5 \u00faltimos ejercicios de la 12\u00aa relaci\u00f3n en la que se plantea la resoluci\u00f3n de distintos problemas matem\u00e1ticos. En concreto, el producto, por plegado, de los n\u00fameros que verifican una propiedad,&#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":[186],"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\/1846"}],"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=1846"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1846\/revisions"}],"predecessor-version":[{"id":2868,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1846\/revisions\/2868"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1846"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1846"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1846"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}