Distancia de Hamming
La distancia de Hamming entre dos listas es el número de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre «roma» y «loba» es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).
Definir la función
|
1 |
distancia :: Eq a => [a] -> [a] -> Int |
tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,
|
1 2 3 4 5 6 7 |
distancia "romano" "comino" == 2 distancia "romano" "camino" == 3 distancia "roma" "comino" == 2 distancia "roma" "camino" == 3 distancia "romano" "ron" == 1 distancia "romano" "cama" == 2 distancia "romano" "rama" == 1 |
Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad
|
1 |
distancia(xs,ys) = 0 si, y sólo si, xs = ys |
y, en el caso de que no se verifique, modificar ligeramente la propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
import Test.QuickCheck -- 1ª definición: distancia :: Eq a => [a] -> [a] -> Int distancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x /= y] -- 2ª definición: distancia2 :: Eq a => [a] -> [a] -> Int distancia2 [] ys = 0 distancia2 xs [] = 0 distancia2 (x:xs) (y:ys) | x /= y = 1 + distancia2 xs ys | otherwise = distancia2 xs ys -- La propiedad es prop_distancia1 :: [Int] -> [Int] -> Bool prop_distancia1 xs ys = (distancia xs ys == 0) == (xs == ys) -- La comprobación es -- ghci> quickCheck prop_distancia1 -- *** Failed! Falsifiable (after 2 tests and 1 shrink): -- [] -- [1] -- -- En efecto, -- ghci> distancia [] [1] == 0 -- True -- ghci> [] == [1] -- False -- -- La primera modificación es restringir la propiedad a lista de igual -- longitud: prop_distancia2 :: [Int] -> [Int] -> Property prop_distancia2 xs ys = length xs == length ys ==> (distancia xs ys == 0) == (xs == ys) -- La comprobación es -- ghci> quickCheck prop_distancia2 -- *** Gave up! Passed only 33 tests. -- Nota. La propiedad se verifica, pero al ser la condición demasiado -- restringida sólo 33 de los casos la cumple. -- La segunda restricción es limitar las listas a la longitud de la más -- corta: prop_distancia3 :: [Int] -> [Int] -> Bool prop_distancia3 xs ys = (distancia xs ys == 0) == (take n xs == take n ys) where n = min (length xs) (length ys) -- La comprobación es -- ghci> quickCheck prop_distancia3 -- +++ OK, passed 100 tests. |
Pensamiento
En mi soledad/
he visto cosas muy claras,
que no son verdad.Antonio Machado