Menu Close

Intersección de listas infinitas crecientes

José A. Alonso,

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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.