Distancia de Hamming
Enunciado
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
-- 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 -- distancia :: Eq a => [a] -> [a] -> Int -- tal que (distancia xs ys) es la distancia de Hamming entre xs e -- ys. Por ejemplo, -- 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 -- 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 |
import Test.QuickCheck -- 1ª definición (por comprensión): distancia :: Eq a => [a] -> [a] -> Int distancia xs ys = sum [1 | (x,y) <- zip xs ys, x /= y] -- 2ª definición (por recursió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. |