Lista muy decreciente

José A. Alonso

31-03-2021

Una lista de números es muy decreciente si cada elemento es menor que la suma de los restantes. Por ejemplo, [19,9,6,2] es muy decreciente ya que

19 > 9 + 6 + 2,
9 > 6 + 2 y
6 > 2

En cambio, [19,8,6,2] no lo es ya que 8 = 6 + 2.

Definir la función

   muyDecreciente :: [Integer] -> Bool

tal que (muyDecreciente xs) se verifica si xs es muy decreciente. Por ejemplo,

   muyDecreciente [19,9,6,2]  ==  True
   muyDecreciente [19,8,6,2]  ==  False
   muyDecreciente [2^k | k <- [60000,59999..0]]  ==  True

Soluciones

-- 1ª solución
-- ===========

muyDecreciente :: [Integer] -> Bool
muyDecreciente []     = True
muyDecreciente (x:xs) = x > sum xs && muyDecreciente xs

-- 2ª solución
-- ===========

muyDecreciente2 :: [Integer] -> Bool
muyDecreciente2 = snd . aux
  where aux []     = (0,True)
        aux (x:xs) = (x + s, x > s && b)
          where (s,b) = aux xs

-- 3ª solución
-- ===========

muyDecreciente3 :: [Integer] -> Bool
muyDecreciente3 xs =
  and (zipWith (>) xs (tail (scanr1 (+) xs)))

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> muyDecreciente [2^k | k <- [10000,9999..0]]
--    True
--    (6.72 secs, 48,095,728,720 bytes)
--    λ> muyDecreciente2 [2^k | k <- [10000,9999..0]]
--    True
--    (0.08 secs, 67,222,960 bytes)
--    λ> muyDecreciente3 [2^k | k <- [10000,9999..0]]
--    True
--    (0.10 secs, 66,664,928 bytes)
--
--    λ> muyDecreciente2 [2^k | k <- [50000,49999..0]]
--    True
--    (1.88 secs, 857,128,312 bytes)
--    λ> muyDecreciente3 [2^k | k <- [50000,49999..0]]
--    True
--    (1.67 secs, 854,326,736 bytes)