-- I1M 2009-10: G1_Rel_7.hs -- 7ª relación de ejercicios (18 de Noviembre) -- Departamento de Ciencias de la Computación e I.A. -- Universidad de Sevilla -- ===================================================================== -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1.1. Definir por recursión la función -- potencia :: Integer -> Integer -> Integer -- tal que (potencia x n) es x elevado al número natural n. Por ejemplo, -- potencia 2 3 => 8 -- --------------------------------------------------------------------- potencia :: Integer -> Integer -> Integer potencia = undefined -- --------------------------------------------------------------------- -- Ejercicio 1.2. Mostrar cómo se evalúa (potencia 2 3). -- --------------------------------------------------------------------- -- El cálculo es -- --------------------------------------------------------------------- -- Ejercicio 1.3. Comprobar con quickCheck que la función potencia es -- equivalente a la predefinida (^). -- --------------------------------------------------------------------- -- La propiedad es prop_potencia :: Integer -> Integer -> Bool prop_potencia x n = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 2.1. Mostrar cómo a partir de la definición -- length :: [a] -> Int -- length [] = 0 -- length.1 -- length (_:xs) = 1 + length xs -- length.2 -- se calcula -- length [1,2,3] -- --------------------------------------------------------------------- -- El cálculo es -- --------------------------------------------------------------------- -- Ejercicio 2.2. Mostrar cómo a partir de la definición -- drop :: Int -> [a] -> [a] -- drop 0 xs = xs -- drop.1 -- drop (n+1) [] = [] -- drop.2 -- drop (n+1) (x:xs) = drop n xs -- drop.3 -- se calcula -- drop 3 [1,2,3,4,5] -- --------------------------------------------------------------------- -- El cálculo es -- --------------------------------------------------------------------- -- Ejercicio 2.3. Mostrar cómo a partir de la definición -- init :: [a] -> [a] -- init [_] = [] -- init.1 -- init (x:xs) = x : init xs -- init.2 -- se calcula -- init [1,2,3] -- --------------------------------------------------------------------- -- El cálculo es -- --------------------------------------------------------------------- -- Ejercicio 3.1.1. Definir por recursión la función -- and' :: [Bool] -> Bool -- tal que (and' xs) se verifica si todos los elementos de xs son -- verdadero. Por ejemplo, -- and' [1+2 < 4, 2:[3] == [2,3]] => True -- and' [1+2 < 3, 2:[3] == [2,3]] => False -- --------------------------------------------------------------------- and' :: [Bool] -> Bool and' = undefined -- --------------------------------------------------------------------- -- Ejercicio 3.1.2. Comprobar con quickCheck que and' es equivalente a -- and. -- --------------------------------------------------------------------- -- La propiedad es prop_and :: [Bool] -> Bool prop_and xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 3.2.1. Definir por recursión la función -- concat' :: [[a]] -> [a] -- tal que (concat' xss) es la lista obtenida concatenando las listas de -- xss. Por ejemplo, -- concat [[1..3],[5..7],[8..10]] => [1,2,3,5,6,7,8,9,10] -- --------------------------------------------------------------------- concat' :: [[a]] -> [a] concat' = undefined -- --------------------------------------------------------------------- -- Ejercicio 3.2.2. Comprobar con quickCheck que concat' es equivalente -- a concat. -- --------------------------------------------------------------------- -- La propiedad es prop_concat :: Eq a => [[a]] -> Bool prop_concat xss = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 3.3.1. Definir por recursión la función -- replicate' :: Int -> a -> [a] -- tal que (replicate' n x) es la lista formado por n copias del -- elemento x. Por ejemplo, -- replicate' 3 2 => [2,2,2] -- --------------------------------------------------------------------- replicate' :: Int -> a -> [a] replicate' = undefined -- --------------------------------------------------------------------- -- Ejercicio 3.3.2. Comprobar con quickCheck que replicate' es -- equivalente a replicate. -- --------------------------------------------------------------------- -- La propiedad (limitada a 100 por eficiencia) es prop_replicate :: Eq a => Int -> a -> Bool prop_replicate n x = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 3.4.1. Definir por recursión la función -- selecciona :: [a] -> Int -> a -- tal que (selecciona xs n) es el n-ésimo elemento de xs. Por ejemplo, -- selecciona [2,3,5,7] 2 => 5 -- --------------------------------------------------------------------- selecciona :: [a] -> Int -> a selecciona = undefined -- --------------------------------------------------------------------- -- Ejercicio 3.4.2. Comprobar con quickCheck que selecciona es -- equivalente a (!!). -- --------------------------------------------------------------------- -- La propiedad sin restricciones es prop_selecciona_1 :: Eq a => [a] -> Int -> Bool prop_selecciona_1 xs n = undefined -- Esta propiedad no se verifica. La comprobación es -- La propiedad con restricciones es prop_selecciona_2 :: Eq a => [a] -> Int -> Property prop_selecciona_2 xs n = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 3.5.1. Definir por recursión la función -- elem' :: Eq a => a -> [a] -> Bool -- tal que (elem' x xs) se verifica si x pertenece a la lista xs. Por -- ejemplo, -- elem' 3 [2,3,5] => True -- elem' 4 [2,3,5] => False -- --------------------------------------------------------------------- elem' :: Eq a => a -> [a] -> Bool elem' = undefined -- --------------------------------------------------------------------- -- Ejercicio 3.5.2. Comprobar con quickCheck que elem' es equivalente a -- elem. -- --------------------------------------------------------------------- -- La propiedad es prop_elem :: Eq a => a -> [a] -> Bool prop_elem x xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 4.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 = undefined -- --------------------------------------------------------------------- -- Ejercicio 4.2. Definir 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 = undefined -- --------------------------------------------------------------------- -- Ejercicio 4.3. Comprobar con quickCheck que la mezcla de dos listas -- ordenadas es una lista ordenada. -- --------------------------------------------------------------------- -- La propiedad es prop_mezcla_ordenada :: Ord a => [a] -> [a] -> Property prop_mezcla_ordenada xs ys = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 4,4. Definir 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 = undefined -- --------------------------------------------------------------------- -- Ejercicio 4.5. Definir 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 -- --------------------------------------------------------------------- -- La definición es esPermutacion :: Eq a => [a] -> [a] -> Bool esPermutacion = undefined -- --------------------------------------------------------------------- -- Ejercicio 4.6. Comprobar con QuickCheck que la inversa de una lista -- es una permutación de la lista. -- --------------------------------------------------------------------- -- La propiedad es prop_InversaEsPermutacion :: [Int] -> Bool prop_InversaEsPermutacion xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 4.7. Comprobar con QuickCheck que la mezcla de dos listas -- es una permutación de su unión. -- --------------------------------------------------------------------- -- La propiedad es prop_mezcla_permutacion xs ys = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 4.8. 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 = undefined -- --------------------------------------------------------------------- -- Ejercicio 4.9. Definir 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 = undefined -- --------------------------------------------------------------------- -- Ejercicio 4.10. Comprobar con QuickCheck que la ordenación por mezcla -- de una lista es una lista ordenada. -- --------------------------------------------------------------------- -- La propiedad es prop_ordMezcla_ordenada :: Ord a => [a] -> Bool prop_ordMezcla_ordenada xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 4.11. 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 :: Ord a => [a] -> Bool prop_ordMezcla_pemutacion xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 5.1. Definir, usando el método de los 5 pasos, la función -- sum' :: [Int] -> Int -- tal que (sum' xs) es la suma de los números de xs. Por ejemplo, -- sum' [2,3,5] => 10 -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 5.2. Definir, usando el método de los 5 pasos, la función -- take' :: Int -> [a] -> [a] -- tal que (take' n xs) es la lista de los n primeros elementos de -- xs. Por ejemplo, -- take' 3 [4..12] => [4,5,6] -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 5.3. Definir, usando el método de los 5 pasos, la función -- last' :: [a] -> a -- tal que (last xs) es el último elemento de xs. Por ejemplo, -- last' [2,3,5] => 5 -- ---------------------------------------------------------------------