{"id":552,"date":"2014-11-07T06:30:22","date_gmt":"2014-11-07T04:30:22","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=552"},"modified":"2021-04-25T17:08:13","modified_gmt":"2021-04-25T15:08:13","slug":"distancia-de-hamming-2014","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/distancia-de-hamming-2014\/","title":{"rendered":"Distancia de Hamming"},"content":{"rendered":"<h4>Enunciado<\/h4>\n<pre lang=\"text\">\n-- La distancia de Hamming entre dos listas es el n\u00famero de posiciones\n-- en que los correspondientes elementos son distintos. Por ejemplo, la\n-- distancia de Hamming entre \"roma\" y \"loba\" es 2 (porque hay 2\n-- posiciones en las que los elementos correspondientes son distintos:\n-- la 1\u00aa y la 3\u00aa). \n-- \n-- Definir la funci\u00f3n\n--    distancia :: Eq a => [a] -> [a] -> Int\n-- tal que (distancia xs ys) es la distancia de Hamming entre xs e\n-- ys. Por ejemplo,\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--\n-- Comprobar con QuickCheck si la distancia de Hamming tiene la\n-- siguiente propiedad\n--    distancia(xs,ys) = 0 si, y s\u00f3lo si, xs = ys\n-- y, en el caso de que no se verifique, modificar ligeramente la\n-- propiedad para obtener una condici\u00f3n necesaria y suficiente de \n-- distancia(xs,ys) = 0.\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n):\ndistancia :: Eq a => [a] -> [a] -> Int\ndistancia xs ys = sum [1 | (x,y) <- zip xs ys, x \/= y] \n\n-- 2\u00aa definici\u00f3n (por recursi\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-- 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","protected":false},"excerpt":{"rendered":"<p>Enunciado &#8212; La distancia de Hamming entre dos listas es el n\u00famero de posiciones &#8212; en que los correspondientes elementos son distintos. Por ejemplo, la &#8212; distancia de Hamming entre \u00abroma\u00bb y \u00abloba\u00bb es 2 (porque hay 2 &#8212; posiciones en las que los elementos correspondientes son distintos: &#8212; la 1\u00aa y la 3\u00aa). &#8211;&#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":[4],"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\/552"}],"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=552"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/552\/revisions"}],"predecessor-version":[{"id":744,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/552\/revisions\/744"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}