La semana en Exercitium (del 21 al 25 de marzo)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Valores de polinomios representados con vectores.
- 2. Ramas de un árbol
- 3. Alfabeto comenzando en un carácter
- 4. Numeración de las ternas de números naturales.
- 5. Ordenación de estructuras
A continuación se muestran las soluciones.
1. Valores de polinomios representados con vectores.
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 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 |
-- --------------------------------------------------------------------- -- Los polinomios se pueden representar mediante vectores usando la -- librería Data.Array. En primer lugar, se define el tipo de los -- polinomios (con coeficientes de tipo a) mediante -- type Polinomio a = Array Int a -- Como ejemplos, definimos el polinomio -- ej_pol1 :: Array Int Int -- ej_pol1 = array (0,4) [(0,6),(1,2),(2,-5),(3,0),(4,7)] -- que representa a 6 + 2x - 5x^2 + 7x^4 y el polinomio -- ej_pol2 :: Array Int Double -- ej_pol2 = array (0,4) [(0,6.5),(1,2),(2,-5.2),(3,0),(4,7)] -- que representa a 6.5 + 2x - 5.2x^2 + 7x^4 -- -- Definir la función -- valor :: Num a => Polinomio a -> a -> a -- tal que (valor p b) es el valor del polinomio p en el punto b. Por -- ejemplo, -- valor ej_pol1 0 == 6 -- valor ej_pol1 1 == 10 -- valor ej_pol1 2 == 102 -- valor ej_pol2 0 == 6.5 -- valor ej_pol2 1 == 10.3 -- valor ej_pol2 3 == 532.7 -- length (show (valor (listArray (0,5*10^5) (repeat 1)) 2)) == 150516 -- --------------------------------------------------------------------- import Data.List (foldl') import Data.Array (Array, (!), array, assocs, bounds, elems, listArray) import Test.QuickCheck type Polinomio a = Array Int a ej_pol1 :: Array Int Int ej_pol1 = array (0,4) [(0,6),(1,2),(2,-5),(3,0),(4,7)] ej_pol2 :: Array Int Double ej_pol2 = array (0,4) [(1,2),(2,-5.2),(4,7),(0,6.5),(3,0)] -- 1ª solución -- =========== valor1 :: Num a => Polinomio a -> a -> a valor1 p b = sum [(p!i)*b^i | i <- [0..n]] where (_,n) = bounds p -- 2ª solución -- =========== valor2 :: Num a => Polinomio a -> a -> a valor2 p b = sum [(p!i)*b^i | i <- [0..length p - 1]] -- 3ª solución -- =========== valor3 :: Num a => Polinomio a -> a -> a valor3 p b = sum [v*b^i | (i,v) <- assocs p] -- 4ª solución -- =========== valor4 :: Num a => Polinomio a -> a -> a valor4 = valorLista4 . elems valorLista4 :: Num a => [a] -> a -> a valorLista4 xs b = sum [(xs !! i) * b^i | i <- [0..length xs - 1]] -- 5ª solución -- =========== valor5 :: Num a => Polinomio a -> a -> a valor5 = valorLista5 . elems valorLista5 :: Num a => [a] -> a -> a valorLista5 [] _ = 0 valorLista5 (x:xs) b = x + b * valorLista5 xs b -- 6ª solución -- =========== valor6 :: Num a => Polinomio a -> a -> a valor6 = valorLista6 . elems valorLista6 :: Num a => [a] -> a -> a valorLista6 xs b = aux xs where aux [] = 0 aux (y:ys) = y + b * aux ys -- 7ª solución -- =========== valor7 :: Num a => Polinomio a -> a -> a valor7 = valorLista7 . elems valorLista7 :: Num a => [a] -> a -> a valorLista7 xs b = foldr (\y r -> y + b * r) 0 xs -- 8ª solución -- =========== valor8 :: Num a => Polinomio a -> a -> a valor8 = valorLista8 . elems valorLista8 :: Num a => [a] -> a -> a valorLista8 xs b = aux 0 (reverse xs) where aux r [] = r aux r (y:ys) = aux (y + r * b) ys -- 9ª solución -- =========== valor9 :: Num a => Polinomio a -> a -> a valor9 = valorLista9 . elems valorLista9 :: Num a => [a] -> a -> a valorLista9 xs b = aux 0 (reverse xs) where aux = foldl (\ r y -> y + r * b) -- 10ª solución -- ============ valor10 :: Num a => Polinomio a -> a -> a valor10 p b = foldl (\ r y -> y + r * b) 0 (reverse (elems p)) -- 11ª solución -- ============ valor11 :: Num a => Polinomio a -> a -> a valor11 p b = foldl' (\ r y -> y + r * b) 0 (reverse (elems p)) -- 12ª solución -- ============ valor12 :: Num a => Polinomio a -> a -> a valor12 p b = sum (zipWith (*) (elems p) (iterate (* b) 1)) -- 13ª solución -- ============ valor13 :: Num a => Polinomio a -> a -> a valor13 p b = foldl' (+) 0 (zipWith (*) (elems p) (iterate (* b) 1)) -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_valor :: [Integer] -> Integer -> Bool prop_valor xs b = all (== valor1 p b) [f p b | f <- [valor2, valor3, valor4, valor5, valor6, valor7, valor8, valor9, valor10, valor11, valor12, valor13]] where p = listArray (0, length xs - 1) xs -- La comprobación es -- λ> quickCheck prop_valor -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (show (valor1 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (7.62 secs, 2,953,933,864 bytes) -- λ> length (show (valor2 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (8.26 secs, 2,953,933,264 bytes) -- λ> length (show (valor3 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (7.49 secs, 2,954,733,184 bytes) -- λ> length (show (valor4 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (84.80 secs, 2,956,333,712 bytes) -- λ> length (show (valor5 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (1.34 secs, 1,307,347,416 bytes) -- λ> length (show (valor6 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (1.26 secs, 1,308,114,752 bytes) -- λ> length (show (valor7 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (1.21 secs, 1,296,843,456 bytes) -- λ> length (show (valor8 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (1.28 secs, 1,309,591,744 bytes) -- λ> length (show (valor9 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (1.27 secs, 1,299,191,672 bytes) -- λ> length (show (valor10 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (1.30 secs, 1,299,191,432 bytes) -- λ> length (show (valor11 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (0.23 secs, 1,287,654,752 bytes) -- λ> length (show (valor12 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (0.75 secs, 1,309,506,968 bytes) -- λ> length (show (valor13 (listArray (0,10^5) (repeat 1)) 2)) -- 30104 -- (0.22 secs, 1,298,867,128 bytes) |
La elaboración de las soluciones se encuentran en el siguiente vídeo
2. Ramas de un árbol
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 |
-- --------------------------------------------------------------------- -- Los árboles se pueden representar mediante el siguiente tipo de datos -- data Arbol a = N a [Arbol a] -- deriving Show -- Por ejemplo, los árboles -- 1 3 -- / \ /|\ -- 2 3 / | \ -- | 5 4 7 -- 4 | /\ -- 6 2 1 -- se representan por -- ej1, ej2 :: Arbol Int -- ej1 = N 1 [N 2 [],N 3 [N 4 []]] -- ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []] -- -- Definir la función -- ramas :: Arbol b -> [[b]] -- tal que (ramas a) es la lista de las ramas del árbol a. Por ejemplo, -- ramas ej1 == [[1,2],[1,3,4]] -- ramas ej2 == [[3,5,6],[3,4],[3,7,2],[3,7,1]] -- --------------------------------------------------------------------- import Test.QuickCheck data Arbol a = N a [Arbol a] deriving Show ej1, ej2 :: Arbol Int ej1 = N 1 [N 2 [],N 3 [N 4 []]] ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]] -- 1ª solución ramas1 :: Arbol b -> [[b]] ramas1 (N x []) = [[x]] ramas1 (N x as) = [x : xs | a <- as, xs <- ramas1 a] -- 2ª solución ramas2 :: Arbol b -> [[b]] ramas2 (N x []) = [[x]] ramas2 (N x as) = concat (map (map (x:)) (map ramas2 as)) -- 3ª solución ramas3 :: Arbol b -> [[b]] ramas3 (N x []) = [[x]] ramas3 (N x as) = concat (map (map (x:) . ramas3) as) -- 4ª solución ramas4 :: Arbol b -> [[b]] ramas4 (N x []) = [[x]] ramas4 (N x as) = concatMap (map (x:) . ramas4) as -- 5ª solución ramas5 :: Arbol a -> [[a]] ramas5 (N x []) = [[x]] ramas5 (N x xs) = map ramas5 xs >>= map (x:) -- Comprobación de la equivalencia de las definiciones -- =================================================== -- (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo, -- λ> sample (arbolArbitrario 4 :: Gen (Arbol Int)) -- N 0 [N 0 []] -- N 1 [N 1 [N (-2) [N (-1) [N (-1) [N (-1) [N 1 []]]]]],N (-1) [N 2 []]] -- N 1 [N (-2) [],N 0 [N (-4) [N (-2) []]]] -- N (-4) [N 1 [],N 0 [N 6 [N (-4) []],N 2 [N 3 []]]] -- N (-7) [N (-7) [N (-3) []]] -- N (-2) [N (-8) []] -- N (-3) [N 3 [N 2 []]] -- N (-12) [N 5 [],N 0 []] -- N 14 [N 13 [N (-12) []],N 11 [],N 8 [N (-13) []]] -- N (-12) [N (-6) [N 16 [N (-14) [N (-1) []]]]] -- N (-5) [] arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario n = do x <- arbitrary ms <- sublistOf [0 .. n `div` 2] as <- mapM arbolArbitrario ms return (N x as) -- Arbol es una subclase de Arbitraria instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario -- La propiedad es prop_arbol :: Arbol Int -> Bool prop_arbol a = all (== ramas1 a) [ramas2 a, ramas3 a, ramas4 a, ramas5 a] -- La comprobación es -- λ> quickCheck prop_arbol -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> ej600 <- generate (arbolArbitrario 600 :: Gen (Arbol Int)) -- λ> length (ramas1 ej600) -- 1262732 -- (1.92 secs, 1,700,238,488 bytes) -- λ> length (ramas2 ej600) -- 1262732 -- (1.94 secs, 2,549,877,280 bytes) -- λ> length (ramas3 ej600) -- 1262732 -- (1.99 secs, 2,446,508,472 bytes) -- λ> length (ramas4 ej600) -- 1262732 -- (1.67 secs, 2,090,469,104 bytes) -- λ> length (ramas5 ej600) -- 1262732 -- (1.66 secs, 2,112,198,232 bytes) |
La elaboración de las soluciones se encuentran en el siguiente vídeo
3. Alfabeto comenzando en un carácter
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 |
-- --------------------------------------------------------------------- -- Definir la función -- alfabetoDesde :: Char -> String -- tal que (alfabetoDesde c) es el alfabeto, en minúscula, comenzando en -- el carácter c, si c es una letra minúscula y comenzando en 'a', en -- caso contrario. Por ejemplo, -- alfabetoDesde 'e' == "efghijklmnopqrstuvwxyzabcd" -- alfabetoDesde 'a' == "abcdefghijklmnopqrstuvwxyz" -- alfabetoDesde '7' == "abcdefghijklmnopqrstuvwxyz" -- alfabetoDesde '{' == "abcdefghijklmnopqrstuvwxyz" -- alfabetoDesde 'B' == "abcdefghijklmnopqrstuvwxyz" -- --------------------------------------------------------------------- import Data.Char (isLower, isAscii) import Test.QuickCheck -- 1ª solución alfabetoDesde1 :: Char -> String alfabetoDesde1 c = dropWhile (<c) ['a'..'z'] ++ takeWhile (<c) ['a'..'z'] -- 2ª solución alfabetoDesde2 :: Char -> String alfabetoDesde2 c = ys ++ xs where (xs,ys) = span (<c) ['a'..'z'] -- 3ª solución alfabetoDesde3 :: Char -> String alfabetoDesde3 c = ys ++ xs where (xs,ys) = break (==c) ['a'..'z'] -- 4ª solución alfabetoDesde4 :: Char -> String alfabetoDesde4 c | 'a' <= c && c <= 'z' = [c..'z'] ++ ['a'..pred c] | otherwise = ['a'..'z'] -- 5ª solución alfabetoDesde5 :: Char -> String alfabetoDesde5 c | isLower c = [c..'z'] ++ ['a'..pred c] | otherwise = ['a'..'z'] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_alfabetoDesde :: Property prop_alfabetoDesde = forAll (arbitrary `suchThat` isAscii) $ \c -> all (== alfabetoDesde1 c) [f c | f <- [alfabetoDesde2, alfabetoDesde3, alfabetoDesde4, alfabetoDesde5]] -- La comprobación es -- λ> quickCheck prop_alfabetoDesde -- +++ OK, passed 100 tests. |
La elaboración de las soluciones se encuentran en el siguiente vídeo
4. Numeración de las ternas de números naturales.
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 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
-- --------------------------------------------------------------------- -- Las ternas de números naturales se pueden ordenar como sigue -- (0,0,0), -- (0,0,1),(0,1,0),(1,0,0), -- (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0), -- (0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),... -- ... -- -- Definir la función -- posicion :: (Int,Int,Int) -> Int -- tal que (posicion (x,y,z)) es la posición de la terna de números -- naturales (x,y,z) en la ordenación anterior. Por ejemplo, -- posicion (0,1,0) == 2 -- posicion (0,0,2) == 4 -- posicion (0,1,1) == 5 -- -- Comprobar con QuickCheck que -- + la posición de (x,0,0) es x(x²+6x+11)/6 -- + la posición de (0,y,0) es y(y²+3y+ 8)/6 -- + la posición de (0,0,z) es z(z²+3z+ 2)/6 -- + la posición de (x,x,x) es x(9x²+14x+7)/2 -- --------------------------------------------------------------------- import Data.List (elemIndex) import Data.Maybe (fromJust) import Test.QuickCheck -- 1ª solución -- =========== posicion1 :: (Int,Int,Int) -> Int posicion1 t = aux 0 ternas where aux n (t':ts) | t' == t = n | otherwise = aux (n+1) ts -- ternas es la lista ordenada de las ternas de números naturales. Por ejemplo, -- λ> take 9 ternas -- [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0)] ternas :: [(Int,Int,Int)] ternas = [(x,y,n-x-y) | n <- [0..], x <- [0..n], y <- [0..n-x]] -- 2ª solución -- =========== posicion2 :: (Int,Int,Int) -> Int posicion2 t = head [n | (n,t') <- zip [0..] ternas, t' == t] -- 3ª solución -- =========== posicion3 :: (Int,Int,Int) -> Int posicion3 t = indice t ternas -- (indice x ys) es el índice de x en ys. Por ejemplo, -- indice 5 [0..] == 5 indice :: Eq a => a -> [a] -> Int indice x ys = length (takeWhile (/= x) ys) -- 4ª solución -- =========== posicion4 :: (Int,Int,Int) -> Int posicion4 t = fromJust (elemIndex t ternas) -- 5ª solución -- =========== posicion5 :: (Int,Int,Int) -> Int posicion5 = fromJust . (`elemIndex` ternas) -- Equivalencia -- ============ -- La propiedad es prop_posicion_equiv :: NonNegative Int -> NonNegative Int -> NonNegative Int -> Bool prop_posicion_equiv (NonNegative x) (NonNegative y) (NonNegative z) = all (== posicion1 (x,y,z)) [f (x,y,z) | f <- [ posicion2 , posicion3 , posicion4 , posicion5 ]] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> posicion1 (147,46,116) -- 5000000 -- (5.84 secs, 2,621,428,184 bytes) -- λ> posicion2 (147,46,116) -- 5000000 -- (3.63 secs, 2,173,230,200 bytes) -- λ> posicion3 (147,46,116) -- 5000000 -- (2.48 secs, 1,453,229,880 bytes) -- λ> posicion4 (147,46,116) -- 5000000 -- (1.91 secs, 1,173,229,840 bytes) -- λ> posicion5 (147,46,116) -- 5000000 -- (1.94 secs, 1,173,229,960 bytes) -- En lo que sigue, usaremos la 5ª definición posicion :: (Int,Int,Int) -> Int posicion = posicion5 -- Propiedades -- =========== -- La 1ª propiedad es prop_posicion1 :: NonNegative Int -> Bool prop_posicion1 (NonNegative x) = posicion (x,0,0) == x * (x^2 + 6*x + 11) `div` 6 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion1 -- +++ OK, passed 100 tests. -- La 2ª propiedad es prop_posicion2 :: NonNegative Int -> Bool prop_posicion2 (NonNegative y) = posicion (0,y,0) == y * (y^2 + 3*y + 8) `div` 6 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion2 -- +++ OK, passed 100 tests. -- La 3ª propiedad es prop_posicion3 :: NonNegative Int -> Bool prop_posicion3 (NonNegative z) = posicion (0,0,z) == z * (z^2 + 3*z + 2) `div` 6 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion3 -- +++ OK, passed 100 tests. -- La 4ª propiedad es prop_posicion4 :: NonNegative Int -> Bool prop_posicion4 (NonNegative x) = posicion (x,x,x) == x * (9 * x^2 + 14 * x + 7) `div` 2 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion4 -- +++ OK, passed 100 tests. |
La elaboración de las soluciones se encuentran en el siguiente vídeo
5. Ordenación de estructuras
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 |
-- --------------------------------------------------------------------- -- Las notas de los dos primeros exámenes se pueden representar mediante -- el siguiente tipo de dato -- data Notas = Notas String Int Int -- deriving (Read, Show, Eq) -- Por ejemplo, (Notas "Juan" 6 5) representar las notas de un alumno -- cuyo nombre es Juan, la nota del primer examen es 6 y la del segundo -- es 5. -- -- Definir la función -- ordenadas :: [Notas] -> [Notas] -- tal que (ordenadas ns) es la lista de las notas ns ordenadas -- considerando primero la nota del examen 2, a continuación la del -- examen 1 y finalmente el nombre. Por ejemplo, -- λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 3 7] -- [Notas "Juan" 6 5,Notas "Luis" 3 7] -- λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 3 4] -- [Notas "Luis" 3 4,Notas "Juan" 6 5] -- λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 7 4] -- [Notas "Luis" 7 4,Notas "Juan" 6 5] -- λ> ordenadas [Notas "Juan" 6 4, Notas "Luis" 7 4] -- [Notas "Juan" 6 4,Notas "Luis" 7 4] -- λ> ordenadas [Notas "Juan" 6 4, Notas "Luis" 5 4] -- [Notas "Luis" 5 4,Notas "Juan" 6 4] -- λ> ordenadas [Notas "Juan" 5 4, Notas "Luis" 5 4] -- [Notas "Juan" 5 4,Notas "Luis" 5 4] -- λ> ordenadas [Notas "Juan" 5 4, Notas "Eva" 5 4] -- [Notas "Eva" 5 4,Notas "Juan" 5 4] -- --------------------------------------------------------------------- import Data.List (sort, sortBy) import Test.QuickCheck data Notas = Notas String Int Int deriving (Read, Show, Eq) -- 1ª solución ordenadas1 :: [Notas] -> [Notas] ordenadas1 ns = [Notas n x y | (y,x,n) <- sort [(y1,x1,n1) | (Notas n1 x1 y1) <- ns]] -- 2ª solución ordenadas2 :: [Notas] -> [Notas] ordenadas2 ns = map (\(y,x,n) -> Notas n x y) (sort [(y1,x1,n1) | (Notas n1 x1 y1) <- ns]) -- 3ª solución ordenadas3 :: [Notas] -> [Notas] ordenadas3 ns = sortBy (\(Notas n1 x1 y1) (Notas n2 x2 y2) -> compare (y1,x1,n1) (y2,x2,n2)) ns -- 4ª solución -- =========== instance Ord Notas where Notas n1 x1 y1 <= Notas n2 x2 y2 = (y1,x1,n1) <= (y2,x2,n2) ordenadas4 :: [Notas] -> [Notas] ordenadas4 = sort -- Comprobación de equivalencia -- ============================ -- notasArbitraria es un generador aleatorio de notas. Por ejemplo, -- λ> sample notasArbitraria -- Notas "achjkqruvxy" 3 3 -- Notas "abfgikmptuvy" 10 10 -- Notas "degjmptvwx" 7 9 -- Notas "cdefghjmnoqrsuw" 0 9 -- Notas "bcdfikmstuxz" 1 8 -- Notas "abcdhkopqsvwx" 10 7 -- Notas "abghiklnoqstvwx" 0 0 -- Notas "abfghklmnoptuvx" 4 9 -- Notas "bdehjkmpqsxyz" 0 4 -- Notas "afghijmopsvwz" 3 7 -- Notas "bdefghjklnoqx" 2 3 notasArbitraria :: Gen Notas notasArbitraria = do n <- sublistOf ['a'..'z'] x <- chooseInt (0, 10) y <- chooseInt (0, 10) return (Notas n x y) -- Notas es una subclase de Arbitrary instance Arbitrary Notas where arbitrary = notasArbitraria -- La propiedad es prop_ordenadas :: [Notas] -> Bool prop_ordenadas ns = all (== ordenadas1 ns) [f ns | f <- [ordenadas2, ordenadas3, ordenadas4]] -- La comprobación es -- λ> quickCheck prop_ordenadas -- +++ OK, passed 100 tests. |
La elaboración de las soluciones se encuentran en el siguiente vídeo