Menu Close

Etiqueta: Recursión

Definición por recursión

La bandera tricolor

El problema de la bandera tricolor consiste en lo siguiente: Dada un lista de objetos xs que pueden ser rojos, amarillos o morados, se pide devolver una lista ys que contiene los elementos de xs, primero los rojos, luego los amarillos y por último los morados.

-- Definir el tipo de dato Color para representar los colores con los
-- constructores R, A y M correspondientes al rojo, azul y morado y la
-- función 
--    banderaTricolor :: [Color] -> [Color]
-- tal que (banderaTricolor xs) es la bandera tricolor formada con los
-- elementos de xs. Por ejemplo,
--    bandera [M,R,A,A,R,R,A,M,M]  ==  [R,R,R,A,A,A,M,M,M]
--    bandera [M,R,A,R,R,A]        ==  [R,R,R,A,A,M]

Soluciones

import Data.List
 
data Color = R | A | M
             deriving (Show, Eq, Ord)
 
-- 1ª definición (con sort):
banderaTricolor :: [Color] -> [Color]
banderaTricolor = sort
 
-- 2ª definición (por comprensión):
banderaTricolor2 :: [Color] -> [Color]
banderaTricolor2 xs = color R ++ color A ++ color M 
    where color c = [x | x <- xs, x == c]
 
-- 3ª definición (por comprensión y concat):
banderaTricolor3 :: [Color] -> [Color]
banderaTricolor3 xs =
    concat [[x | x <- xs, x == c] | c <- [A,R,M]]
 
-- 4ª definición (por recursión):
banderaTricolor4 :: [Color] -> [Color]
banderaTricolor4 xs = aux xs ([],[],[])
    where aux []     (as,rs,ms) = as ++ rs ++ ms
          aux (A:xs) (as,rs,ms) = aux xs (A:as,   rs,   ms)
          aux (R:xs) (as,rs,ms) = aux xs (  as, R:rs,   ms)
          aux (M:xs) (as,rs,ms) = aux xs (  as,   rs, M:ms)
 
-- 5ª definición (por recursión):
banderaTricolor5 :: [Color] -> [Color]
banderaTricolor5 xs = aux xs (0,0,0)
    where aux []     (as,rs,ms) = replicate as A ++ 
                                  replicate rs R ++
                                  replicate ms M
          aux (A:xs) (as,rs,ms) = aux xs (1+as,   rs,   ms)
          aux (R:xs) (as,rs,ms) = aux xs (  as, 1+rs,   ms)
          aux (M:xs) (as,rs,ms) = aux xs (  as,   rs, 1+ms)

Iguales al siguiente

Enunciado

-- Definir la función
--    igualesAlSiguiente :: Eq a => [a] -> [a]
-- tal que (igualesAlSiguiente xs) es la lista de los elementos de xs
-- que son iguales a su siguiente. Por ejemplo,
--    igualesAlSiguiente [1,2,2,2,3,3,4]  ==  [2,2,3]
--    igualesAlSiguiente [1..10]          ==  []

Soluciones

import Data.List (group)
 
-- 1ª definición (por comprensión):
igualesAlSiguiente :: Eq a => [a] -> [a]
igualesAlSiguiente xs =
    [x | (x,y) <- zip xs (tail xs), x == y]
 
-- 2ª definición (por recursión):
igualesAlSiguiente2 :: Eq a => [a] -> [a]
igualesAlSiguiente2 (x:y:zs) | x == y    = x : igualesAlSiguiente2 (y:zs)
                             | otherwise = igualesAlSiguiente2 (y:zs)
igualesAlSiguiente2 _                    = []
 
-- 3ª definición (con concat y comprensión):
igualesAlSiguiente3 :: Eq a => [a] -> [a]
igualesAlSiguiente3 xs = concat [ys | (_:ys) <- group xs]
 
-- 4ª definición (con concat y map):
igualesAlSiguiente4 :: Eq a => [a] -> [a]
igualesAlSiguiente4 xs = concat (map tail (group xs))