Menu Close

Inserciones por posición

Definir la función

   inserta :: [a] -> [[a]] -> [[a]]

tal que (inserta xs yss) es la lista obtenida insertando

  • el primer elemento de xs como primero en la primera lista de yss,
  • el segundo elemento de xs como segundo en la segunda lista de yss (si la segunda lista de yss tiene al menos un elemento),
  • el tercer elemento de xs como tercero en la tercera lista de yss (si la tercera lista de yss tiene al menos dos elementos),

y así sucesivamente. Por ejemplo,

   inserta [1,2,3] [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,3,8]]
   inserta [1,2,3] [[4,7],[] ,[9,5,8]]  ==  [[1,4,7],[],   [9,5,3,8]]
   inserta [1,2]   [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,8]]
   inserta [1,2,3] [[4,7],[6]]          ==  [[1,4,7],[6,2]]
   inserta "tad"   ["odo","pra","naa"]  ==  ["todo","para","nada"]

Nota: Este ejercicio es parte del examen del grupo 2 del 4 de diciembre.

Soluciones

-- 1ª solución
-- ===========
 
inserta :: [a] -> [[a]] -> [[a]]
inserta xs yss = aux xs yss 0 where
    aux [] yss _ = yss
    aux xs []  _ = []
    aux (x:xs) (ys:yss) n 
        | length us == n = (us ++ x : vs) : aux xs yss (n+1)
        | otherwise      = ys : aux xs yss (n+1)
        where (us,vs) = splitAt n ys
 
-- 2ª solución
-- ===========
 
inserta2 :: [a] -> [[a]] -> [[a]]
inserta2 xs yss =  
    [ins n x ys | (n,x,ys) <- zip3 [0..] xs yss] ++ drop (length xs) yss
 
ins :: Int -> a -> [a] -> [a]
ins n x ys | length ys < n  = ys
           | otherwise      = take n ys ++ x : drop n ys
 
-- Comparación de eficiencia
-- =========================
 
--    λ> let n = 10000 in length (inserta [1..n] (replicate n (replicate n 0)))
--    10000
--    (3.28 secs, 6,400,568,776 bytes)
--    λ> let n = 10000 in length (inserta2 [1..n] (replicate n (replicate n 0)))
--    10000
--    (0.02 secs, 0 bytes)

2 soluciones de “Inserciones por posición

  1. fracruzam
    inserta :: [a] -> [[a]] -> [[a]]
    inserta = aux2 0 False
      where aux :: Int -> Bool -> a -> [a] -> [a]
            aux 0 _ x  ys                 = x : ys
            aux n b x (y:ys) 
                     | b                  = y : aux (n-1) b x ys
                     | length (y:ys) >= n = aux n True x (y:ys)
                     | otherwise          = y:ys
            aux _ _ _  ys                 = ys
            aux2 :: Int -> Bool -> [a] -> [[a]] -> [[a]]
            aux2 n b (x:xs) (y:ys) = aux n b x y : aux2 (n+1) b xs ys
            aux2 _ _  _      ys    = ys
     
    -- *Main> inserta [1,2,3] [[],[],[4]]
    -- [[1],[],[4]]
  2. Chema Cortés
    inserta :: [a] -> [[a]] -> [[a]]
    inserta xs yss =  [ ins n x ys | (n,x,ys) <- zip3 [0..] xs yss ]
                   ++ drop (length xs) yss
     
    ins :: Int -> a -> [a] -> [a]
    ins n x ys | length ys < n  = ys
               | otherwise      = take n ys ++ x : drop n ys

Escribe tu solución

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