Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operaci\u00f3n binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operaci\u00f3n a los elementos i y j es el j-\u00e9simo elemento del i-\u00e9simo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta m\u00f3dulo 3 en A son<\/p>\n
\n 0 1 2 0 2 1\n 1 2 0 1 0 2\n 2 0 1 2 1 0\n Suma Resta\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n conmutativa :: [[Int]] -> Bool\n<\/pre>\ntal que (conmutativa xss) se verifica si la operaci\u00f3n cuya tabla es xss es conmutativa. Por ejemplo,<\/p>\n
\n conmutativa [[0,1,2],[1,0,1],[2,1,0]] == True\n conmutativa [[0,1,2],[1,0,0],[2,1,0]] == False\n conmutativa [[i+j `mod` 2000 | j <- [0..1999]] | i <- [0..1999]] == True\n conmutativa [[i-j `mod` 2000 | j <- [0..1999]] | i <- [0..1999]] == False\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (transpose)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nconmutativa :: [[Int]] -> Bool\nconmutativa xss =\n and [producto i j == producto j i | i <- [0..n-1], j <- [0..n-1]]\n where producto i j = (xss !! i) !! j\n n = length xss\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nconmutativa2 :: [[Int]] -> Bool\nconmutativa2 [] = True\nconmutativa2 t@(xs:xss) = xs == map head t\n && conmutativa2 (map tail xss)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nconmutativa3 :: [[Int]] -> Bool\nconmutativa3 xss = xss == transpose xss\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nconmutativa4 :: [[Int]] -> Bool\nconmutativa4 = (==) <*> transpose \n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- Para comprobar la equivalencia se define el tipo de tabla de\n-- operciones binarias:\nnewtype Tabla = T [[Int]]\n deriving Show\n\n-- genTabla es un generador de tablas de operciones binaria. Por ejemplo,\n-- \u03bb> sample genTabla\n-- T [[2,0,0],[1,2,1],[1,0,2]]\n-- T [[0,3,0,1],[0,1,2,1],[0,2,1,2],[3,0,0,2]]\n-- T [[2,0,1],[1,0,0],[2,1,2]]\n-- T [[1,0],[0,1]]\n-- T [[1,1],[0,1]]\n-- T [[1,1,2],[1,0,1],[2,1,0]]\n-- T [[4,4,3,0,2],[2,2,0,1,2],[4,0,1,0,0],[0,4,4,3,3],[3,0,4,2,1]]\n-- T [[3,4,1,4,1],[2,4,4,0,4],[1,2,1,4,3],[3,1,4,4,2],[4,1,3,2,3]]\n-- T [[2,0,1],[2,1,0],[0,2,2]]\n-- T [[3,2,0,3],[2,1,1,1],[0,2,1,0],[3,3,2,3]]\n-- T [[2,0,2,0],[0,0,3,1],[1,2,3,2],[3,3,0,2]]\ngenTabla :: Gen Tabla\ngenTabla = do\n n <- choose (2,20)\n xs <- vectorOf (n^2) (elements [0..n-1])\n return (T (separa n xs))\n\n-- (separa n xs) es la lista obtenidaseparando los elementos de xs en\n-- grupos de n elementos. Por ejemplo,\n-- separa 3 [1..9] == [[1,2,3],[4,5,6],[7,8,9]]\nsepara :: Int -> [a] -> [[a]]\nsepara _ [] = []\nsepara n xs = take n xs : separa n (drop n xs)\n\n-- Generaci\u00f3n arbitraria de tablas\ninstance Arbitrary Tabla where\n arbitrary = genTabla\n\n-- La propiedad es\nprop_conmutativa :: Tabla -> Bool\nprop_conmutativa (T xss) =\n conmutativa xss == conmutativa2 xss &&\n conmutativa2 xss == conmutativa3 xss &&\n conmutativa2 xss == conmutativa4 xss\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_conmutativa\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- Para las comparaciones se usar\u00e1 la funci\u00f3n tablaSuma tal que\n-- (tablaSuma n) es la tabla de la suma m\u00f3dulo n en [0..n-1]. Por\n-- ejemplo, \n-- tablaSuma 3 == [[0,1,2],[1,2,3],[2,3,4]]\ntablaSuma :: Int -> [[Int]]\ntablaSuma n =\n [[i + j `mod` n | j <- [0..n-1]] | i <- [0..n-1]]\n\n-- La comparaci\u00f3n es\n-- \u03bb> conmutativa (tablaSuma 400)\n-- True\n-- (1.92 secs, 147,608,696 bytes)\n-- \u03bb> conmutativa2 (tablaSuma 400)\n-- True\n-- (0.14 secs, 63,101,112 bytes)\n-- \u03bb> conmutativa3 (tablaSuma 400)\n-- True\n-- (0.10 secs, 64,302,608 bytes)\n-- \u03bb> conmutativa4 (tablaSuma 400)\n-- True\n-- (0.10 secs, 61,738,928 bytes)\n-- \n-- \u03bb> conmutativa2 (tablaSuma 2000)\n-- True\n-- (1.81 secs, 1,569,390,480 bytes)\n-- \u03bb> conmutativa3 (tablaSuma 2000)\n-- True\n-- (3.07 secs, 1,601,006,840 bytes)\n-- \u03bb> conmutativa4 (tablaSuma 2000)\n-- True\n-- (3.14 secs, 1,536,971,288 bytes)\n<\/pre>\nPensamiento<\/h4>\n\n\"Nuestras horas son minutos cuando esperamos saber, y siglos cuando
\nsabemos lo que se puede aprender.\"<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operaci\u00f3n binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operaci\u00f3n a los elementos i y j es el j-\u00e9simo…<\/p>\n","protected":false},"author":1,"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":[5],"tags":[100,8,28,462,11,45,68],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4468"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=4468"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4468\/revisions"}],"predecessor-version":[{"id":4510,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4468\/revisions\/4510"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4468"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4468"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}