Inserciones por posición
Definir la función
|
1 |
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,
|
1 2 3 4 5 |
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 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 29 30 31 32 |
-- 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 Comentarios