{"id":4297,"date":"2018-11-12T06:00:21","date_gmt":"2018-11-12T04:00:21","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4297"},"modified":"2019-01-17T15:39:17","modified_gmt":"2019-01-17T13:39:17","slug":"distancia-de-hamming","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/distancia-de-hamming\/","title":{"rendered":"Distancia de Hamming"},"content":{"rendered":"<p>La distancia de Hamming entre dos listas es el n\u00famero de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre \u00abroma\u00bb y \u00abloba\u00bb es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1\u00aa y la 3\u00aa).<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   distancia :: Eq a => [a] -> [a] -> Int\n<\/pre>\n<p>tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   distancia \"romano\" \"comino\"  ==  2\n   distancia \"romano\" \"camino\"  ==  3\n   distancia \"roma\"   \"comino\"  ==  2\n   distancia \"roma\"   \"camino\"  ==  3\n   distancia \"romano\" \"ron\"     ==  1\n   distancia \"romano\" \"cama\"    ==  2\n   distancia \"romano\" \"rama\"    ==  1\n<\/pre>\n<p>Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad<\/p>\n<pre lang=\"text\">\n   distancia(xs,ys) = 0 si, y s\u00f3lo si, xs = ys\n<\/pre>\n<p>y, en el caso de que no se verifique, modificar ligeramente la propiedad para obtener una condici\u00f3n necesaria y suficiente de  distancia(xs,ys) = 0.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n:\ndistancia :: Eq a => [a] -> [a] -> Int\ndistancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x \/= y] \n\n-- 2\u00aa definici\u00f3n:\ndistancia2 :: Eq a => [a] -> [a] -> Int\ndistancia2 [] ys = 0\ndistancia2 xs [] = 0\ndistancia2 (x:xs) (y:ys) | x \/= y    = 1 + distancia2 xs ys\n                         | otherwise = distancia2 xs ys\n\n-- La propiedad es\nprop_distancia1 :: [Int] -> [Int] -> Bool\nprop_distancia1 xs ys =\n    (distancia xs ys == 0) == (xs == ys)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_distancia1\n--    *** Failed! Falsifiable (after 2 tests and 1 shrink): \n--    []\n--    [1]\n-- \n-- En efecto,\n--    ghci> distancia [] [1] == 0\n--    True\n--    ghci> [] == [1]\n--    False\n-- \n-- La primera modificaci\u00f3n es restringir la propiedad a lista de igual\n-- longitud: \nprop_distancia2 :: [Int] -> [Int] -> Property\nprop_distancia2 xs ys =\n    length xs == length ys ==> \n    (distancia xs ys == 0) == (xs == ys)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_distancia2\n--    *** Gave up! Passed only 33 tests.\n\n-- Nota. La propiedad se verifica, pero al ser la condici\u00f3n demasiado\n-- restringida s\u00f3lo 33 de los casos la cumple.\n\n-- La segunda restricci\u00f3n es limitar las listas a la longitud de la m\u00e1s\n-- corta: \nprop_distancia3 :: [Int] -> [Int] -> Bool\nprop_distancia3 xs ys =\n    (distancia xs ys == 0) == (take n xs == take n ys)\n    where n = min (length xs) (length ys)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_distancia3\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nEn mi soledad\/<br \/>\nhe visto cosas muy claras,<br \/>\nque no son verdad.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>La distancia de Hamming entre dos listas es el n\u00famero de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre \u00abroma\u00bb y \u00abloba\u00bb es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1\u00aa y la 3\u00aa). Definir la funci\u00f3n distancia :: Eq a&#8230;<\/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":[8,28,84,6,40,47,146,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4297"}],"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=4297"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4297\/revisions"}],"predecessor-version":[{"id":4575,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4297\/revisions\/4575"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}