Listas duplicadas
Se observa que en la cadena «aabbccddeffgg» todos los caracteres están duplicados excepto el ‘e’. Al añadirlo obtenemos la lista «aabbccddeeffgg» y se dice que esta última está duplicada.
También se observa que «aaaabbbccccdd» no está duplicada (porque hay un número impar de ‘b’ consecutivas). Añadiendo una ‘b’ se obtiene «aaaabbbbccccdd» que está duplicada.
Definir las funciones
1 2 |
esDuplicada :: Eq a => [a] -> Bool duplica :: Eq a => [a] -> [a] |
tales que
- (esDuplicada xs) se verifica si xs es una lista duplicada. Por ejemplo,
1 2 3 4 |
esDuplicada "aabbccddeffgg" == False esDuplicada "aabbccddeeffgg" == True esDuplicada "aaaabbbccccdd" == False esDuplicada "aaaabbbbccccdd" == True |
- (duplica xs) es la lista obtenida duplicando los elementos de xs que no lo están. Por ejemplo,
1 2 3 4 5 |
duplica "b" == "bb" duplica "abba" == "aabbaa" duplica "Betis" == "BBeettiiss" duplica [1,1,1] == [1,1,1,1] duplica [1,1,1,1] == [1,1,1,1] |
Comprobar con QuickCheck que, para cualquier lista de enteros xs, se verifica la siguiente propiedad:
1 |
esDuplicada (duplica xs) |
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 |
import Data.List (group) import Test.QuickCheck -- 1ª definición de esDuplicada esDuplicada :: Eq a => [a] -> Bool esDuplicada [] = True esDuplicada [_] = False esDuplicada (x:y:zs) = x == y && esDuplicada zs -- 2ª definición de esDuplicada esDuplicada2 :: Eq a => [a] -> Bool esDuplicada2 = all (even . length) . group -- 1ª definición de duplica duplica :: Eq a => [a] -> [a] duplica [] = [] duplica [x] = [x,x] duplica (x:y:zs) | x == y = x : x : duplica zs | otherwise = x : x : duplica (y:zs) -- 2ª definición de duplica duplica2 :: Eq a => [a] -> [a] duplica2 xs = concatMap dupl (group xs) where dupl ys@(y:_) | (even.length) ys = ys | otherwise = y : ys -- Propiedad prop_duplica_esDuplicada :: [Int] -> Bool prop_duplica_esDuplicada xs = esDuplicada (duplica xs) -- La comprobación es -- λ> quickCheck prop_duplica_esDuplicada -- +++ OK, passed 100 tests. |
4 Comentarios