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.