Ir al contenido principal

Mayor sección inicial sin repetidos

Definir la función

seccion :: Eq a => [a] -> [a]

tal que (seccion xs) es el mayor sección inicial de xs que no contiene ningún elemento repetido. Por ejemplo:

seccion [1,2,3,2,4,5]                      == [1,2,3]
seccion "caceres"                          == "ca"
length (seccion ([1..7531] ++ [1..10^9]))  ==  7531

Soluciones

import Data.List (inits, nub)

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

seccion1 :: Eq a => [a] -> [a]
seccion1 = last . filter (\ys -> nub ys == ys) . inits

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

seccion2 :: Eq a => [a] -> [a]
seccion2 xs = aux xs []
    where aux [] ys = reverse ys
          aux (x:xs) ys | x `elem` ys = reverse ys
                        | otherwise   = aux xs (x:ys)

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

--    λ> last (seccion1 [1..10^3])
--    1000
--    (6.19 secs, 59,174,640 bytes)
--    λ> last (seccion2 [1..10^3])
--    1000
--    (0.04 secs, 0 bytes)