import Data.List (group, genericLength)
import Test.QuickCheck (Arbitrary, Gen,
arbitrary, frequency, suchThat, quickCheck)
-- 1ª solución
-- ===========
ausente1 :: Integral a => [a] -> a
ausente1 (x1:xs@(x2:x3:_))
| d1 == d2 = ausente1 xs
| d1 == 2 * d2 = x1 + d2
| d2 == 2 * d1 = x2 + d1
where d1 = x2 - x1
d2 = x3 - x2
-- 2ª solución
-- ===========
ausente2 :: Integral a => [a] -> a
ausente2 s@(x1:x2:x3:_)
| x1 + x3 /= 2 * x2 = x1 + (x3 - x2)
| otherwise = head [a | (a,b) <- zip [x1,x2..] s
, a /= b]
-- 3ª solución
-- ===========
ausente3 :: Integral a => [a] -> a
ausente3 xs@(x1:x2:_)
| null us = x1 + v
| otherwise = x2 + u * genericLength (u:us)
where ((u:us):(v:_):_) = group (zipWith (-) (tail xs) xs)
-- Comprobación de equivalencia
-- ============================
-- Tipo de progresiones aritméticas con un término ausente.
newtype PAconAusente = PA [Integer]
deriving Show
-- Generación de progresiones aritméticas con un término ausente.
progresionConAusenteArbitraria :: Gen PAconAusente
progresionConAusenteArbitraria = do
x <- arbitrary
d <- arbitrary `suchThat` (/= 0)
n <- arbitrary `suchThat` (> 2)
k <- arbitrary `suchThat` (> 0)
let (as,_:bs) = splitAt k [x,x+d..]
frequency [(1,return (PA (as ++ bs))),
(1,return (PA (take (length as + n) (as ++ bs))))]
-- Inclusión del tipo PAconAusente en Arbitrary.
instance Arbitrary PAconAusente where
arbitrary = progresionConAusenteArbitraria
-- La propiedad es
prop_ausente :: PAconAusente -> Bool
prop_ausente (PA xs) =
all (== ausente1 xs)
[ausente2 xs,
ausente3 xs]
-- La comprobación es
-- λ> quickCheck prop_ausente
-- +++ OK, passed 100 tests.
-- Comparación de eficiencia
-- =========================
-- La comparación es
-- λ> let n = 10^6 in ausente1 ([1..n] ++ [n+2])
-- 1000001
-- (1.15 secs, 560,529,520 bytes)
-- λ> let n = 10^6 in ausente2 ([1..n] ++ [n+2])
-- 1000001
-- (0.33 secs, 336,530,680 bytes)
-- λ> let n = 10^6 in ausente3 ([1..n] ++ [n+2])
-- 1000001
-- (0.50 secs, 498,047,584 bytes)