Distancia de Hamming

PorJosé A. Alonso 7-noviembre-201425-abril-2021

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.

3 Comentarios

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.

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 dice:

7-noviembre-2014 a las 23:38

La propiedad

Haskell

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

1
2
3

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

Haskell

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

1
2
3

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

y su comprobación es

Haskell

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

1
2
3
4

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

Se encuentra un contraejemplo. En efecto,

Haskell

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

1
2
3
4

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

La condición suficiente es

Haskell

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

1
2
3

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

y su comprobación es

Haskell

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

1
2

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

Haskell

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

1
2
3

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,

Haskell

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

1
2
3

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

y su comprobación es

Haskell

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

1
2

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

Haskell

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

1
2

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

y su comprobación es

Haskell

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

1
2
3
4

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

Haskell

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

1
2
3

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

y su comprobación es

Haskell

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

1
2

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

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

Haskell

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

1
2
3

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

y su comprobación es

Haskell

ghci> quickCheck prop_ejemplo2 *** Failed! Falsifiable (after 4 tests): 1 0

1
2
3
4

ghci> quickCheck prop_ejemplo2
*** Failed! Falsifiable (after 4 tests):
1
0

Responder

Tamara Royán González dice:

8-noviembre-2014 a las 12:56

Haskell

distancia :: Eq a => [a] -> [a] -> Int distancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x /= y]

1
2

distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x /= y]

Responder

Distancia de Hamming

Enunciado

Soluciones

3 Comentarios

Leave a Reply to Jesús Navas OrozcoCancel reply

Entradas recientes

Buscar

Correo electrónico

Enunciado

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Leave a Reply to Jesús Navas OrozcoCancel reply

Entradas recientes

Buscar

Correo electrónico