Siembra de listas
Definir la función
1 |
siembra :: [Int] -> [Int] |
tal que (siembra xs) es la lista ys obtenida al repartir cada elemento x de la lista xs poniendo un 1 en las x siguientes posiciones de la lista ys. Por ejemplo,
1 2 3 |
siembra [4] == [0,1,1,1,1] siembra [0,2] == [0,0,1,1] siembra [4,2] == [0,1,2,2,1] |
El tercer ejemplo se obtiene sumando la siembra de 4 en la posición 0 (como el ejemplo 1) y el 2 en la posición 1 (como el ejemplo 2). Otros ejemplos son
1 2 3 4 5 |
siembra [0,4,2] == [0,0,1,2,2,1] siembra [3] == [0,1,1,1] siembra [3,4,2] == [0,1,2,3,2,1] siembra [3,2,1] == [0,1,2,3] sum $ siembra [1..2500] == 3126250 |
Comprobar con QuickCheck que la suma de los elementos de (siembra xs) es igual que la suma de los de xs.
Nota 1: Se supone que el argumento es una lista de números no negativos y que se puede ampliar tanto como sea necesario para repartir los elementos.
Nota 2: Este ejercicio es parte del examen del grupo 3 del 2 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
import Test.QuickCheck -- 1ª solución -- =========== siembra1 :: [Int] -> [Int] siembra1 = suma . brotes -- (brotes xs) es la lista de los brotes obtenido sembrando los -- elementos de xs. Por ejemplo, -- brotes [3,4,2] == [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]] brotes :: [Int] -> [[Int]] brotes xs = aux xs 1 where aux (x:xs) n = (replicate n 0 ++ replicate x 1) : aux xs (n+1) aux _ _ = [] -- (suma xss) es la suma de los elementos de xss (suponiendo que al -- final de cada elemento se continua con ceros). Por ejemplo, -- suma [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]] == [0,1,2,3,2,1] suma :: [[Int]] -> [Int] suma = foldr1 aux where aux [] ys = ys aux xs [] = xs aux (x:xs) (y:ys) = (x+y) : aux xs ys -- 2ª solución -- =========== siembra2 :: [Int] -> [Int] siembra2 [] = [] siembra2 (x:xs) = mezcla (siembraElemento x) (0 : siembra2 xs) siembraElemento :: Int -> [Int] siembraElemento x = 0 : replicate x 1 mezcla :: [Int] -> [Int] -> [Int] mezcla xs ys = take (max (length xs) (length ys)) (zipWith (+) (xs ++ repeat 0) (ys ++ repeat 0)) -- 3ª solución -- =========== siembra3 :: [Int] -> [Int] siembra3 [] = [] siembra3 xs = aux xs 0 (repeat 0) where aux [] _ ys = cosecha ys aux (x:xs) n ys = aux xs (n+1) (zipWith (+) brotes ys) where brotes = replicate (n+1) 0 ++ replicate x 1 ++ repeat 0 -- (cosecha xs) es la lista formada por los ceros iniciales de xs y los -- elementos siguientes hasta que vuelve a aparecer el 0. Por ejemplo, -- cosecha [0,0,3,5,2,0,9] == [0,0,3,5,2] -- cosecha ([0,0,3,5,2] ++ repeat 0) == [0,0,3,5,2] cosecha :: [Int] -> [Int] cosecha xs = ys ++ takeWhile (>0) zs where (ys,zs) = span (==0) xs -- 4ª solución -- =========== siembra4 :: [Int] -> [Int] siembra4 [] = [] siembra4 xs = aux xs [] (repeat 0) where aux [] ys zs = reverse ys ++ takeWhile (>0) zs aux (x:xs) ys (z:zs) = aux xs (z:ys) (zipWith (+) brotes zs) where brotes = replicate x 1 ++ repeat 0 -- Comparación de eficiencia -- ========================= -- λ> sum $ siembra1 [1..2000] -- 2001000 -- (9.44 secs, 1,894,065,928 bytes) -- ghci> sum $ siembra2 [1..2000] -- 2001000 -- (5.92 secs, 936900576 bytes) -- ghci> sum $ siembra3 [1..2000] -- 2001000 -- (1.59 secs, 836847072 bytes) -- ghci> sum $ siembra4 [1..2000] -- 2001000 -- (1.68 secs, 570492392 bytes) -- En lo que sigue usaremos la 2ª definición siembra :: [Int] -> [Int] siembra = siembra2 -- Verificación -- ============ -- La propiedad es prop_siembra :: [Int] -> Bool prop_siembra xs = sum (siembra1 ys) == sum ys where ys = map (\x -> 1 + abs x) xs -- La comprobación es -- λ> quickCheck prop_siembra -- +++ OK, passed 100 tests. |
4 Comentarios