Intersección de listas infinitas crecientes
Definir la función
|
1 |
interseccion :: Ord a => [[a]] -> [a] |
tal que (interseccion xss) es la intersección de la lista no vacía de listas infinitas crecientes xss; es decir, la lista de los elementos que pertenecen a todas las listas de xss. Por ejemplo,
|
1 2 3 4 |
λ> take 10 (interseccion [[2,4..],[3,6..],[5,10..]]) [30,60,90,120,150,180,210,240,270,300] λ> take 10 (interseccion [[2,5..],[3,5..],[5,7..]]) [5,11,17,23,29,35,41,47,53,59] |
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 |
-- 1ª solución -- =========== interseccion :: Ord a => [[a]] -> [a] interseccion [xs] = xs interseccion (xs:ys:zss) = interseccionDos xs (interseccion (ys:zss)) interseccionDos :: Ord a => [a] -> [a] -> [a] interseccionDos (x:xs) (y:ys) | x == y = x : interseccionDos xs ys | x < y = interseccionDos (dropWhile (<y) xs) (y:ys) | otherwise = interseccionDos (x:xs) (dropWhile (<x) ys) -- 2ª solución -- =========== interseccion2 :: Ord a => [[a]] -> [a] interseccion2 = foldl1 interseccionDos -- 3ª solución -- =========== interseccion3 :: Ord a => [[a]] -> [a] interseccion3 (xs:xss) = [x | x <- xs, all (x `pertenece`) xss] pertenece :: Ord a => a -> [a] -> Bool pertenece x xs = x == head (dropWhile (<x) xs) |
Pensamiento
Dios no es el creador del mundo (según Martín), sino el creador de la nada.
Antonio Machado
3 Comentarios