Menu Close

Mezcla de infinitas listas infinitas

José A. Alonso,

Definir la función

   mezclaTodas :: Ord a => [[a]] -> [a]

tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,

   ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
   [2,3,4,5,6,7,8,9,10,11]
   ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
   [2,4,6,8,9,10,12,14,16,18]

Soluciones

mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
    where xmezcla (x:xs) ys = x : mezcla xs ys
 
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys
Avanzado
, , ,

3 soluciones de “Mezcla de infinitas listas infinitas”

  1. Responder
    carruirui3 
    mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas ((x:xs):xss) = x : mezcla2 xs (mezclaTodas xss)
 
mezcla2 :: Ord a => [a] -> [a] -> [a]
mezcla2 (x:xs) (y:ys) | x < y = x : mezcla2 xs (y:ys)
                      | y < x = y : mezcla2 (x:xs) ys
                      | otherwise = x : mezcla2 xs ys
  2. Responder
    josejuan 
    import Data.List (insert, group)
 
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = map head . group . f where f ((x:xs):xss) = x : f (insert xs xss)
  3. Responder
    Carlos 
    merge :: Ord a => [a] -> [a] -> [a]
merge (x:xs) (y:ys)
  | x <  y = x:merge xs (y:ys)
  | x >  y = y:merge (x:xs) ys
  | x == y = x:merge xs ys
 
mergeAll :: Ord a => [[a]] -> [a]
mergeAll (xs:xss) = xmerge xs (mergeAll xss)
  where xmerge (x:xs) ys = x:merge xs ys
 
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = mergeAll

Escribe tu solución

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