Agrupación por orden de aparición
Definir la función
1 |
agrupacion :: Eq a => [a] -> [a] |
tal que (agrupacion xs) es la lista obtenida agrupando los elementos de xs según su primera aparición. Por ejemplo,
1 2 |
agrupacion [3,1,5,1,7,1,5,3] == [3,3,1,1,1,5,5,7] agrupacion "babcacb" == "bbbaacc" |
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 |
import Data.List (nub, partition) -- 1ª definición agrupacion :: Eq a => [a] -> [a] agrupacion [] = [] agrupacion (x:xs) = x : filter (==x) xs ++ agrupacion (filter (/=x) xs) -- 2ª definición agrupacion2 :: Eq a => [a] -> [a] agrupacion2 xs = concat [filter (x==) xs | x <- nub xs] -- 3ª definición agrupacion3 :: Eq a => [a] -> [a] agrupacion3 [] = [] agrupacion3 (x:xs) = x : ys ++ agrupacion3 zs where (ys,zs) = partition (==x) xs -- Comparación de eficiencia -- λ> import Data.List (cycle) -- λ> :set +s -- λ> sum (agrupacion (take (10^7) (cycle [0,1,2,3]))) -- 15000000 -- (24.40 secs, 3,173,123,368 bytes) -- λ> sum (agrupacion2 (take (10^7) (cycle [0,1,2,3]))) -- 15000000 -- (13.71 secs, 2,333,129,416 bytes) -- λ> sum (agrupacion3 (take (10^7) (cycle [0,1,2,3]))) -- 15000000 -- (22.33 secs, 5,080,127,944 bytes) |
8 Comentarios