Agrupamiento de consecutivos iguales
Definir las funciones
1 2 |
agrupa :: Eq a => [a] -> [(a,Int)] expande :: [(a,Int)] -> [a] |
tales que
- (agrupa xs) es la lista obtenida agrupando las ocurrencias consecutivas de elementos de xs junto con el número de dichas ocurrencias. Por ejemplo:
1 |
agrupa "aaabzzaa" == [('a',3),('b',1),('z',2),('a',2)] |
- (expande xs) es la lista expandida correspondiente a ps (es decir, es la lista xs tal que la comprimida de xs es ps. Por ejemplo,
1 |
expande [('a',2),('b',3),('a',1)] == "aabbba" |
Comprobar con QuickCheck que dada una lista de enteros, si se la agrupa y después se expande se obtiene la lista inicial.
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
import Data.List (group) import Test.QuickCheck -- Definiciones de agrupa -- ====================== -- 1ª definición (por recursión) agrupa :: Eq a => [a] -> [(a,Int)] agrupa xs = aux xs 1 where aux (x:y:zs) n | x == y = aux (y:zs) (n+1) | otherwise = (x,n) : aux (y:zs) 1 aux [x] n = [(x,n)] aux [] _ = [] -- 2ª definición (por recursión usando takeWhile): agrupa2 :: Eq a => [a] -> [(a,Int)] agrupa2 [] = [] agrupa2 (x:xs) = (x,1 + length (takeWhile (==x) xs)) : agrupa2 (dropWhile (==x) xs) -- 3ª definición (por comprensión usando group): agrupa3 :: Eq a => [a] -> [(a,Int)] agrupa3 xs = [(head ys,length ys) | ys <- group xs] -- 4ª definición (usando map y group): agrupa4 :: Eq a => [a] -> [(a,Int)] agrupa4 = map (\xs -> (head xs, length xs)) . group -- Definiciones de expande -- ======================= -- 1ª definición (por comprensión) expande :: [(a,Int)] -> [a] expande ps = concat [replicate k x | (x,k) <- ps] -- 2ª definición (por concatMap) expande2 :: [(a,Int)] -> [a] expande2 = concatMap (\(x,k) -> replicate k x) -- 3ª definición (por recursión) expande3 :: [(a,Int)] -> [a] expande3 [] = [] expande3 ((x,n):ps) = replicate n x ++ expande3 ps -- Comprobación -- ============ -- La propiedad es prop_expande_agrupa :: [Int] -> Bool prop_expande_agrupa xs = expande (agrupa xs) == xs -- La comprobación es -- ghci> quickCheck prop_expande_agrupa -- +++ OK, passed 100 tests. |