Menu Close

Distancia de Hamming

José A. Alonso,

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.

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.
Medio
, , , , , , ,

3 soluciones de “Distancia de Hamming”

  1. Responder
    Jesús Navas Orozco 
    import Test.QuickCheck
 
distancia :: Eq a => [a] -> [a] -> Int
distancia [] _ = 0
distancia _ [] = 0
distancia (x:xs) (y:ys) | x == y = distancia xs ys
                        | x /= y = 1 + distancia xs ys
 
prop_distancia :: Eq a => [a] -> [a] -> Property
prop_distancia xs ys = 
    xs == ys ==> distancia xs ys == 0 && distancia xs ys == 0 ==> xs == ys
 
-- La comprobación es:
--    *Main> quickCheck prop_distancia
--    *** Gave up! Passed only 44 tests.
 
-- Aunque salga este mensaje, lo cierto es que hay que añadir la
-- condición de que tanto xs como ys pueden ser la lista vacía, pues: 
--    *Main> distancia [] "asd"
--    0
-- y evidentemente en este caso xs/= ys. Por lo tanto, la propiedad quedaría:
 
prop_distancia2 :: Eq a => [a] -> [a] -> Property
prop_distancia2 xs ys = 
    xs == ys || xs == [] || ys == [] ==> d == 0 && d == 0 ==> xs == ys|| xs == [] || ys == []
    where d = distancia xs ys
 
-- Comprobación:
--    *Main> quickCheck prop_distancia'
--    *** Gave up! Passed only 73 tests.
 
-- Sin embargo, el resultado que vemos es el parecido, aunque la
-- propiedad ahora ha cambiado.
    • Responder
      José A. Alonso Publicar autor

      La propiedad

      prop_distancia :: Eq a => [a] -> [a] -> Property
prop_distancia xs ys = 
    xs == ys ==> distancia xs ys == 0 && distancia xs ys == 0 ==> xs == ys

      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

      prop_distanciaCN :: [Int] -> [Int] -> Property
prop_distanciaCN xs ys = 
    distancia xs ys == 0 ==> xs == ys

      y su comprobación es

      ghci> quickCheck prop_distanciaCN
*** Failed! Falsifiable (after 4 tests and 3 shrinks): 
[0]
[]

      Se encuentra un contraejemplo. En efecto,

      ghci> distancia [0] [] == 0
True
ghci> [0] == []
False

      La condición suficiente es

      prop_distanciaCS :: [Int] -> [Int] -> Property
prop_distanciaCS xs ys = 
    xs == ys ==> distancia xs ys == 0

      y su comprobación es

      ghci> quickCheck prop_distanciaCS
*** Gave up! Passed only 9 tests.

      Para entender lo que expresa la prop_distancia, se pueden escribir los paréntesis implícitos y la propiedad queda como

      prop_distancia :: Eq a => [a] -> [a] -> Property
prop_distancia xs ys = 
    xs == ys ==> (distancia xs ys == 0 && distancia xs ys == 0 ==> xs == ys)

      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,

      prop_tautologia :: Bool -> Bool -> Property
prop_tautologia p q =
    p ==> (q && q ==> p)

      y su comprobación es

      ghci> quickCheck prop_tautologia
+++ OK, passed 100 tests.

      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

      prop_equivalencia :: Bool -> Bool -> Bool
prop_equivalencia p q = p == q

      y su comprobación es

      ghci> quickCheck prop_equivalencia
*** Failed! Falsifiable (after 1 test): 
True
False

      Un ejemplo análogo es cómo expresar la equivalencia entre (x /= 1) y (x =/= 2). Una forma incorrecta de expresarla es

      prop_ejemplo1 :: Int -> Int -> Property
prop_ejemplo1 x y =
    x /= 1 ==> x /= 2 && x /= 2 ==> x /= 1

      y su comprobación es

      ghci> quickCheck prop_ejemplo1
+++ OK, passed 100 tests.

      Una forma correcta de expresar la equivalencia entre (x /= 1) y (x =/= 2) es

      prop_ejemplo2 :: Int -> Int -> Bool
prop_ejemplo2 x y =
    (x /= 1) == (x /= 2)

      y su comprobación es

      ghci> quickCheck prop_ejemplo2
*** Failed! Falsifiable (after 4 tests): 
1
0
  2. Responder
    Tamara Royán González 
    distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x /= y]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.