Distancia de Hamming

PorJosé A. Alonso 12-noviembre-201817-enero-2019

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

1	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

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

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

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.

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

7 Comentarios

distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = sum [1 | (a,b) <- zip xs ys , a /= b]

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

-- Da errores con listas del tipo [] y [()] 

-- La implicación en el otro sentido siempre se cumple
prop_distancia' :: Eq a => [a] -> [a] -> Property
prop_distancia' xs ys = xs == ys ==> distancia xs ys == 0

-- La condición necesaria y suficiente para que se cumpla que la
-- (distancia xs ys == 0) es que las posiciones que se comparan en
-- los dos tienen que ser iguales. Además, tienen que ser del mismo tipo.

distancia :: Eq a => [a] -> [a] -> Int

distancia xs ys = sum [1 | (a,b) <- zip xs ys , a /= b]

prop_distancia :: Eq a => [a] -> [a] -> Property

prop_distancia xs ys = distancia xs ys == 0 ==> xs == ys

-- Da errores con listas del tipo [] y [()]

-- La implicación en el otro sentido siempre se cumple

prop_distancia' :: Eq a => [a] -> [a] -> Property

prop_distancia' xs ys = xs == ys ==> distancia xs ys == 0

-- La condición necesaria y suficiente para que se cumpla que la

-- (distancia xs ys == 0) es que las posiciones que se comparan en

-- los dos tienen que ser iguales. Además, tienen que ser del mismo tipo.

Responder

distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys
  | length xs < length ys =
    sum [1 | n <- [0..length xs - 1], xs !! n /= ys !! n]
  | otherwise =
    sum [1 | n <- [0..length ys - 1], xs !! n /= ys !! n]

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

-- El caso [] , [()] no es válido

-- quickCheckWith (stdArgs {maxSize=19}) prop_distancia, el tamaño
-- máximo debe ser 19, sino da el siguiente error
-- "*** Gave ----up! Passed only 79 tests."

distancia :: Eq a => [a] -> [a] -> Int

distancia xs ys

| length xs < length ys =

sum [1 | n <- [0..length xs - 1], xs !! n /= ys !! n]

| otherwise =

sum [1 | n <- [0..length ys - 1], xs !! n /= ys !! n]

prop_distancia :: Eq a => [a] -> [a] -> Property

prop_distancia xs ys =

xs == ys ==> distancia xs ys==0 && distancia xs ys==0 ==> xs==ys

-- El caso [] , [()] no es válido

-- quickCheckWith (stdArgs {maxSize=19}) prop_distancia, el tamaño

-- máximo debe ser 19, sino da el siguiente error

-- "*** Gave ----up! Passed only 79 tests."

Responder

distancia :: Eq a => [a] -> [a] -> Int
distancia [] ys = 0
distancia xs [] = 0
distancia (x:xs) (y:ys)
  | x == y    = 0 + distancia xs ys 
  | otherwise = 1 + distancia xs ys

prop_distancia xs ys =
     xs == ys ==> distancia xs ys == 0
  && distancia xs ys == 0 ==> xs == ys

-- λ> quickCheck prop_distancia
-- *** Gave up! Passed only 45 tests.

-- Errores en [] y [()]

distancia :: Eq a => [a] -> [a] -> Int

distancia [] ys = 0

distancia xs [] = 0

distancia (x:xs) (y:ys)

| x == y = 0 + distancia xs ys

| otherwise = 1 + distancia xs ys

prop_distancia xs ys =

xs == ys ==> distancia xs ys == 0

&& distancia xs ys == 0 ==> xs == ys

-- λ> quickCheck prop_distancia

-- *** Gave up! Passed only 45 tests.

-- Errores en [] y [()]

Responder

import Test.QuickCheck

distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = sum [1 | (a,b) <- zip xs ys, a /= b]

prop_distancia :: Eq a => [a] -> [a] -> Bool
prop_distancia xs ys
  | xs == ys  = distancia xs ys == 0
  | otherwise = not (distancia xs ys == 0)

-- Da errores con listas del tipo [] y [()].

-- Modificando ligeramente la propiedad anterior obtenemos:
-- distancia (xs,ys) = 0 y length(xs) = lenght(ys) si, y sólo si, xs = ys

prop_distancia' :: Eq a => [a] -> [a] -> Bool
prop_distancia' xs ys
  | length xs == length ys && distancia xs ys == 0 = xs == ys
  | otherwise                                      = xs /= ys

-- Esta propiedad sí es cierta: OK, passed 100 tests.

import Test.QuickCheck

distancia :: Eq a => [a] -> [a] -> Int

distancia xs ys = sum [1 | (a,b) <- zip xs ys, a /= b]

prop_distancia :: Eq a => [a] -> [a] -> Bool

prop_distancia xs ys

| xs == ys = distancia xs ys == 0

| otherwise = not (distancia xs ys == 0)

-- Da errores con listas del tipo [] y [()].

-- Modificando ligeramente la propiedad anterior obtenemos:

-- distancia (xs,ys) = 0 y length(xs) = lenght(ys) si, y sólo si, xs = ys

prop_distancia' :: Eq a => [a] -> [a] -> Bool

prop_distancia' xs ys

| length xs == length ys && distancia xs ys == 0 = xs == ys

| otherwise = xs /= ys

-- Esta propiedad sí es cierta: OK, passed 100 tests.

Responder

distancia :: Eq a => [a] -> [a] -> Int
distancia (x:xs) (y:ys) | x /= y     = 1 + distancia xs ys
                        | otherwise  = distancia xs ys
distancia  _  _                      = 0

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

--    λ> quickCheck prop_distancia
--    *** Failed! Falsifiable (after 2 tests): 
--    [()]
--    []

-- Condición necesaria y suficiente
prop_distancia' :: Eq a => [a] -> [a] -> Property
prop_distancia' xs ys =
  distancia xs ys == 0  && length xs == length ys
  ==> xs == ys 

--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_distancia'
--    +++ OK, passed 100 tests.

distancia :: Eq a => [a] -> [a] -> Int

distancia (x:xs) (y:ys) | x /= y = 1 + distancia xs ys

| otherwise = distancia xs ys

distancia _ _ = 0

prop_distancia :: Eq a => [a] -> [a] -> Property

prop_distancia xs ys = distancia xs ys == 0 ==> xs == ys

-- λ> quickCheck prop_distancia

-- *** Failed! Falsifiable (after 2 tests):

-- [()]

-- []

-- Condición necesaria y suficiente

prop_distancia' :: Eq a => [a] -> [a] -> Property

prop_distancia' xs ys =

distancia xs ys == 0 && length xs == length ys

==> xs == ys

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_distancia'

-- +++ OK, passed 100 tests.

Responder

Una primera definición empleando librerías auxiliares, y una segunda sin ella

import Test.QuickCheck
import Data.List.Utils (countElem)

distancia :: Eq a => [a] -> [a] -> Int
distancia = (countElem True .) . zipWith (/=)

distancia' :: Eq a => [a] -> [a] -> Int
distancia' (x:xs) (y:ys) | x == y    = distancia' xs ys
                         | otherwise = 1 + distancia' xs ys
distancia' _      _      = 0


-- Propiedad
-- =========

-- La propiedad es
prop_distancia1 :: [Int] -> [Int] -> Bool
prop_distancia1 xs ys =
    (distancia xs ys == 0) == (xs == ys)
 
-- La comprobación es
--    λ> quickCheck prop_distancia1
--    *** Failed! Falsifiable (after 4 tests and 2 shrinks): 
--    [0]
--    []
-- Efectivamente,
--    λ> distancia [0] [] == 0
--    True
--    λ> [0] == []
--    False
 
-- Por tanto, restringimos la propiedad a listas 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
--    λ> quickCheck prop_distancia2
--    *** Gave up! Passed only 36 tests.
 
-- La propiedad es correcta, pero la condición es demasiado
-- restringida y sólo puede pasar 36 de los casos.
 
-- Limitamos, por tanto, 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
--    λ> quickCheck prop_distancia3
--    +++ OK, passed 100 tests.

import Test.QuickCheck

import Data.List.Utils (countElem)

distancia :: Eq a => [a] -> [a] -> Int

distancia = (countElem True .) . zipWith (/=)

distancia' :: Eq a => [a] -> [a] -> Int

distancia' (x:xs) (y:ys) | x == y = distancia' xs ys

| otherwise = 1 + distancia' xs ys

distancia' _ _ = 0

-- Propiedad

-- =========

-- La propiedad es

prop_distancia1 :: [Int] -> [Int] -> Bool

prop_distancia1 xs ys =

(distancia xs ys == 0) == (xs == ys)

-- La comprobación es

-- λ> quickCheck prop_distancia1

-- *** Failed! Falsifiable (after 4 tests and 2 shrinks):

-- [0]

-- []

-- Efectivamente,

-- λ> distancia [0] [] == 0

-- True

-- λ> [0] == []

-- False

-- Por tanto, restringimos la propiedad a listas 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

-- λ> quickCheck prop_distancia2

-- *** Gave up! Passed only 36 tests.

-- La propiedad es correcta, pero la condición es demasiado

-- restringida y sólo puede pasar 36 de los casos.

-- Limitamos, por tanto, 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

-- λ> quickCheck prop_distancia3

-- +++ OK, passed 100 tests.

Responder

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

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

-- λ> quickCheck prop_distancia2
-- *** Failed! Falsifiable (after 2 tests): 
-- [()]
-- []

-- Condición necesaria y suficiente

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

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_distancia'
-- +++ OK, passed 100 tests.

distancia :: Eq a => [a] -> [a] -> Int

distancia xs ys = length [(a,b) | (a,b) <- zip xs ys , a /= b]

prop_distancia :: Eq a => [a] -> [a] -> Property

prop_distancia xs ys = distancia xs ys == 0 ==> xs == ys

-- λ> quickCheck prop_distancia2

-- *** Failed! Falsifiable (after 2 tests):

-- [()]

-- []

-- Condición necesaria y suficiente

prop_distancia' :: Eq a => [a] -> [a] -> Property

prop_distancia' xs ys =

distancia xs ys == 0 && length xs == length ys ==> xs == ys

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_distancia'

-- +++ OK, passed 100 tests.

Responder

Distancia de Hamming

Soluciones

Pensamiento

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico