Enunciado
-- 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. |
-- 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
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. |
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.
Se puede imprimir o compartir con
La propiedad
no expresa una condición necesaria y suficiente para que (distancia xs ys == 0). Una forma de expresarla es usando una propiedad para la condición necesaria y otra para la condición suficiente.
La condición necesaria es
y su comprobación es
Se encuentra un contraejemplo. En efecto,
La condición suficiente es
y su comprobación es
Para entender lo que expresa la prop_distancia, se pueden escribir los paréntesis implícitos y la propiedad queda como
Si representamos (xs == ys) por p y (distancia xs ys == 0) por q, la propiedad anterior es isomorfa a la tautología (p -> (q & q -> p)). En efecto,
y su comprobación es
La propiedad anterior no expresa que p syss q. Para expresarlo se puede usar, como vimos antes, una propiedad para la condición necesaria y otra para la condición suficiente. Otra forma de expresar la equivalencia es
y su comprobación es
Un ejemplo análogo es cómo expresar la equivalencia entre (x /= 1) y (x =/= 2). Una forma incorrecta de expresarla es
y su comprobación es
Una forma correcta de expresar la equivalencia entre (x /= 1) y (x =/= 2) es
y su comprobación es