I1M2013: Verificación de la ordenación por mezcla con QuickCheck
En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha estudiado la verificación de propiedades con QuickCheck y, como aplicación, se ha estudiado la verificación de la ordenación por mezcla siguiendo los ejercicios de la relación 9.
Los ejercicios, y sus soluciones, se muestran a continuación:
|
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- El objetivo de esta relación es definir la ordenación por mezclas y -- comprobar su corrección con QuickCheck. import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. Definir por recursión la función -- mezcla :: Ord a => [a] -> [a] -> [a] -- tal que (mezcla xs ys) es la lista obtenida mezclando las listas -- ordenadas xs e ys. Por ejemplo, -- mezcla [2,5,6] [1,3,4] == [1,2,3,4,5,6] -- --------------------------------------------------------------------- mezcla :: Ord a => [a] -> [a] -> [a] mezcla [] ys = ys mezcla xs [] = xs mezcla (x:xs) (y:ys) | x <= y = x : mezcla xs (y:ys) | otherwise = y : mezcla (x:xs) ys -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- mitades :: [a] -> ([a],[a]) -- tal que (mitades xs) es el par formado por las dos mitades en que se -- divide xs tales que sus longitudes difieren como máximo en uno. Por -- ejemplo, -- mitades [2,3,5,7,9] == ([2,3],[5,7,9]) -- --------------------------------------------------------------------- mitades :: [a] -> ([a],[a]) mitades xs = splitAt (length xs `div` 2) xs -- --------------------------------------------------------------------- -- Ejercicio 3. Definir por recursión la función -- ordMezcla :: Ord a => [a] -> [a] -- tal que (ordMezcla xs) es la lista obtenida ordenado xs por mezcla -- (es decir, considerando que la lista vacía y las listas unitarias -- están ordenadas y cualquier otra lista se ordena mezclando las dos -- listas que resultan de ordenar sus dos mitades por separado). Por -- ejemplo, -- ordMezcla [5,2,3,1,7,2,5] == [1,2,2,3,5,5,7] -- --------------------------------------------------------------------- ordMezcla :: Ord a => [a] -> [a] ordMezcla [] = [] ordMezcla [x] = [x] ordMezcla xs = mezcla (ordMezcla ys) (ordMezcla zs) where (ys,zs) = mitades xs -- --------------------------------------------------------------------- -- Ejercicio 4. Definir por recursión la función -- ordenada :: Ord a => [a] -> Bool -- tal que (ordenada xs) se verifica si xs es una lista ordenada. Por -- ejemplo, -- ordenada [2,3,5] == True -- ordenada [2,5,3] == False -- --------------------------------------------------------------------- ordenada :: Ord a => [a] -> Bool ordenada [] = True ordenada [_] = True ordenada (x:y:xs) = x <= y && ordenada (y:xs) -- --------------------------------------------------------------------- -- Ejercicio 5. Comprobar con QuickCheck que la ordenación por mezcla -- de una lista es una lista ordenada. -- --------------------------------------------------------------------- -- La propiedad es prop_ordMezcla_ordenada :: [Int] -> Bool prop_ordMezcla_ordenada xs = ordenada (ordMezcla xs) -- La comprobación es -- ghci> quickCheck prop_ordMezcla_ordenada -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 6. Definir por recursión la función -- borra :: Eq a => a -> [a] -> [a] -- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de -- x en la lista xs. Por ejemplo, -- borra 1 [1,2,1] == [2,1] -- borra 3 [1,2,1] == [1,2,1] -- --------------------------------------------------------------------- borra :: Eq a => a -> [a] -> [a] borra x [] = [] borra x (y:ys) | x == y = ys | otherwise = y : borra x ys -- --------------------------------------------------------------------- -- Ejercicio 7. Definir por recursión la función -- esPermutacion :: Eq a => [a] -> [a] -> Bool -- tal que (esPermutacion xs ys) se verifica si xs es una permutación de -- ys. Por ejemplo, -- esPermutacion [1,2,1] [2,1,1] == True -- esPermutacion [1,2,1] [1,2,2] == False -- --------------------------------------------------------------------- esPermutacion :: Eq a => [a] -> [a] -> Bool esPermutacion [] [] = True esPermutacion [] (y:ys) = False esPermutacion (x:xs) ys = elem x ys && esPermutacion xs (borra x ys) -- --------------------------------------------------------------------- -- Ejercicio 8. Comprobar con QuickCheck que la ordenación por mezcla -- de una lista es una permutación de la lista. -- --------------------------------------------------------------------- -- La propiedad es prop_ordMezcla_pemutacion :: [Int] -> Bool prop_ordMezcla_pemutacion xs = esPermutacion (ordMezcla xs) xs -- La comprobación es -- ghci> quickCheck prop_ordMezcla_pemutacion -- +++ OK, passed 100 tests. |