Segmentos de una lista que verifican una propiedad
He añadido a LógicaMente la siguiente relación de ejercicios que ilustra el uso de las funciones de orden superior en Haskell y la comprobación de sus propiedades con QuickCheck.
|
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 |
-- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck import Text.Show.Functions import Data.List -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- esPrefijo :: Eq a => [a] -> [a] -> Bool -- tal que (esPrefijo xs ys) se verifica si xs es un prefijo de ys; es -- decir una lista de elementos consecutivos de ys empezando por su -- primer elemento. Por ejemplo, -- esPrefijo [2,5] [2,5,3] == True -- esPrefijo [2,5] [2,3,5] == False -- esPrefijo [2,5] [3,2,5] == False -- --------------------------------------------------------------------- esPrefijo :: Eq a => [a] -> [a] -> Bool esPrefijo [] _ = True esPrefijo (x:xs) (y:ys) = x == y && esPrefijo xs ys -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- esSegmento :: Eq a => [a] -> [a] -> Bool -- tal que (esSegmento xs ys) se verifica si xs es un segmento de ys; es -- decir, una lista de elementos consecutivos de ys. Por ejemplo, -- esSegmento [2,5] [2,5,3] == True -- esSegmento [2,5] [2,3,5] == False -- esSegmento [2,5] [3,2,5] == True -- --------------------------------------------------------------------- esSegmento :: Eq a => [a] -> [a] -> Bool esSegmento [] _ = True esSegmento _ [] = False esSegmento xs (y:ys) = esPrefijo xs (y:ys) || esSegmento xs ys -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- segmentos :: (a -> Bool) -> [a] -> [[a]] -- tal que (segmentos p xs) es la lista de los segmentos de xs que -- verifican la propiedad p. Por ejemplo, -- segmentos (>3) [4,2,0,7,0,6,8,9,5,4] == [[4],[7],[6,8,9,5,4]] -- segmentos even [4,2,0,7,0,6,8,9,5,4] == [[4,2,0],[0,6,8],[4]] -- --------------------------------------------------------------------- segmentos :: (a -> Bool) -> [a] -> [[a]] segmentos p [] = [] segmentos p xs = takeWhile p xs : segmentos p (dropWhile (not . p) (dropWhile p xs)) -- --------------------------------------------------------------------- -- Ejercicio 4. Comprobar con QuickCheck que para toda propiedad p y -- toda lista xs, los elementos de (segmentos p xs) son segmentos de -- xs. -- --------------------------------------------------------------------- -- La propiedad es prop_segmentosDaSegmentos :: (Int -> Bool) -> [Int] -> Bool prop_segmentosDaSegmentos p xs = and [esSegmento ys xs | ys <- segmentos p xs] -- La comprobación es -- ghci> quickCheck prop_segmentosDaSegmentos -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 5. Comprobar con QuickCheck que para toda propiedad p y -- toda lista xs, los elementos de los elementos de (segmentos p xs) -- cumplen la propiedad p. -- --------------------------------------------------------------------- -- La propiedad es prop_segmentosCumplen1 :: (Int -> Bool) -> [Int] -> Bool prop_segmentosCumplen1 p xs = and [p x | x <- concat (segmentos p xs)] -- La comprobación es -- ghci> quickCheck prop_segmentosCumplen1 -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 6. Comprobar con QuickCheck que para toda propiedad p y -- toda lista xs, los elementos de xs que no pertenece a ninguno de los -- elementos de (segmentos p xs) no cumplen la propiedad p. -- --------------------------------------------------------------------- -- La propiedad es prop_segmentosCumplen2 :: (Int -> Bool) -> [Int] -> Bool prop_segmentosCumplen2 p xs = and [not (p x) | x <- xs \\ concat (segmentos p xs)] -- La comprobación es -- ghci> quickCheck prop_segmentosCumplen2 -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 7. Comprobar con QuickCheck que para toda propiedad p y -- toda lista xs, los suma de las longitudes de los elementos de -- (segmentos p xs) es el número de elementos de xs que cumplen p. -- --------------------------------------------------------------------- -- La propiedad es prop_segmentosLongitud1 :: (Int -> Bool) -> [Int] -> Bool prop_segmentosLongitud1 p xs = sum [length ys | ys <- segmentos p xs] == length (filter p xs) -- La comprobación es -- ghci> quickCheck prop_segmentosLongitud1 -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 8. Comprobar con QuickCheck que para toda propiedad p y -- toda lista xs, el número de elementos de xs que no pertenecen a -- ninguno de los elementos de (segmentos p xs) es el número de los -- elementos de xs que no cumplen la propiedad p. -- --------------------------------------------------------------------- -- La propiedad es prop_segmentosLongitud2 :: (Int -> Bool) -> [Int] -> Bool prop_segmentosLongitud2 p xs = length (xs \\ concat (segmentos p xs)) == length (filter (not . p) xs) -- La comprobación es -- ghci> quickCheck prop_segmentosLongitud2 -- +++ OK, passed 100 tests. |