Menu Close

Intersección de listas infinitas crecientes

Definir la función

   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,

   λ> 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ª 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

Pensamiento

Alguna vez he pensado
si el alma será la ausencia,
mientras más cerca más lejos;
mientras más lejos más cerca.

Antonio Machado

Medio

5 soluciones de “Intersección de listas infinitas crecientes

  1. frahidzam
    interseccion :: Ord a => [[a]] -> [a]
    interseccion xss = mira (rompe xss)
     
    rompe :: Ord a => [[a]] -> ([a], [[a]])
    rompe xss = (head xss, tail xss)
     
    mira :: Ord a => ([a], [[a]]) -> [a]
    mira (x:xs, yss)
      | and [elem x ys | ys <- map (takeWhile (<= x)) yss] = [x] ++ mira (xs, yss)
      | otherwise                                          = mira (xs,yss)
  2. ireprirod
    interseccion :: Ord a => [[a]] -> [a]
    interseccion (xs:xss) = [x | x <- xs, and [pertenece x ys | ys <- xss]]
     
    pertenece :: Ord a => a -> [a] -> Bool
    pertenece x xs = elem x (takeWhile (<=x) xs)
  3. lucsanand
    interseccion :: Ord a => [[a]] -> [a]
    interseccion (xs:xss)
      | elem [] (xs:xss) = []
      | otherwise        = [x | x <- xs, pertenecer x xss]
     
    pertenecer :: Ord a => a -> [[a]] -> Bool
    pertenecer a []       = True
    pertenecer a (xs:xss) = elem a (takeWhile (<=a) xs) && pertenecer a xss
  4. luipromor
    interseccion :: Ord a => [[a]] -> [a]
    interseccion (xs:xss) = [x | x <- xs, pertenece x xss]
      where pertenece x xss = all (elem x) [takeWhile (<=x) ys | ys <- xss]
  5. adogargon
    interseccion :: Ord a => [[a]] -> [a]
    interseccion (xs:xss) =
      [x | x <-xs, and [ x `elem` ys | ys <- map (takeWhile (<=x)) xss]]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.