Reducción de opuestos
Se considera el siguiente procedimiento de reducción de listas: busca un par de elementos consecutivos iguales pero con signos opuestos, se eliminan dichos elementos y se continúa el proceso hasta que no se encuentren pares de elementos consecutivos iguales pero con signos opuestos. Por ejemplo, la reducción de [-2,1,-1,2,3,4,-3] es
[-2,1,-1,2,3,4,-3] (se elimina el par (1,-1)) -> [-2,2,3,4,-3] (se elimina el par (-2,2)) -> [3,4,-3] (el par (3,-3) no son consecutivos)
Definir la función
reducida :: [Int] -> [Int]
tal que (reducida xs) es la lista obtenida aplicando a xs el de eliminación de pares de elementos consecutivos opuestos. Por ejemplo,
reducida [-2,1,-1,2,3,4,-3] == [3,4,-3] reducida [-2,1,-1,2,3,-4,4,-3] == [] reducida [-2,1,-1,2,5,3,-4,4,-3] == [5] reducida [-2,1,-1,2,5,3,-4,4,-3,-5] == []
Soluciones
-- 1ª solución -- =========== reducida :: [Int] -> [Int] reducida xs | xs == ys = xs | otherwise = reducida ys where ys = paso xs paso :: [Int] -> [Int] paso [] = [] paso [x] = [x] paso (x:y:zs) | x == -y = paso zs | otherwise = x : paso (y:zs) -- 2ª solución -- =========== reducida2 :: [Int] -> [Int] reducida2 xs = aux xs [] where aux [] ys = reverse ys aux (x:xs) (y:ys) | x == -y = aux xs ys aux (x:xs) ys = aux xs (x:ys) -- Comparación de eficiencia -- ========================= -- λ> reducida (take (10^7) (cycle [1,-1])) -- [] -- (9.40 secs, 1,280,127,720 bytes) -- λ> reducida2 (take (10^7) (cycle [1,-1])) -- [] -- (12.16 secs, 2,080,127,560 bytes)