data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]
-- 1ª solución (por recursión):
reducido1 :: Camino -> Camino
reducido1 [] = []
reducido1 (d:ds) | null ds' = [d]
| d == opuesta (head ds') = tail ds'
| otherwise = d:ds'
where ds' = reducido1 ds
opuesta :: Direccion -> Direccion
opuesta N = S
opuesta S = N
opuesta E = O
opuesta O = E
-- 2ª solución (por plegado)
reducido2 :: Camino -> Camino
reducido2 = foldr aux []
where aux N (S:xs) = xs
aux S (N:xs) = xs
aux E (O:xs) = xs
aux O (E:xs) = xs
aux x xs = x:xs
-- 3ª solución
reducido3 :: Camino -> Camino
reducido3 [] = []
reducido3 (N:S:ds) = reducido3 ds
reducido3 (S:N:ds) = reducido3 ds
reducido3 (E:O:ds) = reducido3 ds
reducido3 (O:E:ds) = reducido3 ds
reducido3 (d:ds) | null ds' = [d]
| d == opuesta (head ds') = tail ds'
| otherwise = d:ds'
where ds' = reducido3 ds
-- 4ª solución
reducido4 :: Camino -> Camino
reducido4 ds = reverse (aux ([],ds)) where
aux (N:xs, S:ys) = aux (xs,ys)
aux (S:xs, N:ys) = aux (xs,ys)
aux (E:xs, O:ys) = aux (xs,ys)
aux (O:xs, E:ys) = aux (xs,ys)
aux ( xs, y:ys) = aux (y:xs,ys)
aux ( xs, []) = xs
-- Comparación de eficiencia
-- ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))
-- []
-- (3.87 secs, 460160736 bytes)
-- ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))
-- []
-- (1.16 secs, 216582880 bytes)
-- ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))
-- []
-- (0.58 secs, 98561872 bytes)
-- ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))
-- []
-- (0.64 secs, 176154640 bytes)
--
-- ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))
-- []
-- (5.43 secs, 962694784 bytes)
-- ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))
-- []
-- (9.29 secs, 1722601528 bytes)
--
-- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
-- 400002
-- (4.52 secs, 547004960 bytes)
-- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
-- 400002
-- (2.17 secs, 379049224 bytes)
--
-- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)
-- []
-- (7.35 secs, 537797096 bytes)
-- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)
-- []
-- (2.30 secs, 244553404 bytes)
-- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)
-- []
-- (8.08 secs, 545043608 bytes)
-- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)
-- []
-- (1.96 secs, 205552240 bytes)