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)

[-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]

1	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]   == []

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)

-- 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)

4 Comentarios

reducida :: [Int] -> [Int]
reducida xs = head (filter p (iterate aux xs))

  where aux [] = []
        aux [x] = [x]
        aux (x:y:xs) | x == -y = xs
                     | otherwise = x: aux(y:xs)
        p xs = aux xs == xs

reducida :: [Int] -> [Int]

reducida xs = head (filter p (iterate aux xs))

where aux [] = []

aux [x] = [x]

aux (x:y:xs) | x == -y = xs

| otherwise = x: aux(y:xs)

p xs = aux xs == xs

Responder

reducida :: [Int] -> [Int]
reducida = until aceptable elimConsOpuestos 
  where aceptable = noHayConsOpuestos

elimConsOpuestos :: [Int] -> [Int]
elimConsOpuestos [] = []
elimConsOpuestos [x] = [x]
elimConsOpuestos (x:y:xs)
  | x == -y = elimConsOpuestos xs
  | otherwise = x: elimConsOpuestos (y:xs)

noHayConsOpuestos :: [Int] -> Bool
noHayConsOpuestos xs = elimConsOpuestos xs == xs

reducida :: [Int] -> [Int]

reducida = until aceptable elimConsOpuestos

where aceptable = noHayConsOpuestos

elimConsOpuestos :: [Int] -> [Int]

elimConsOpuestos [] = []

elimConsOpuestos [x] = [x]

elimConsOpuestos (x:y:xs)

| x == -y = elimConsOpuestos xs

| otherwise = x: elimConsOpuestos (y:xs)

noHayConsOpuestos :: [Int] -> Bool

noHayConsOpuestos xs = elimConsOpuestos xs == xs

Responder

reducida :: [Int] -> [Int]
reducida xs = paso xs []
  where paso (y:ys) [] = paso ys [y]
        paso (y:ys) zzs@(z:zs) | y == -z = paso ys zs
                               | otherwise = paso ys (y:zzs)
        paso _ zs = reverse zs

reducida :: [Int] -> [Int]

reducida xs = paso xs []

where paso (y:ys) [] = paso ys [y]

paso (y:ys) zzs@(z:zs) | y == -z = paso ys zs

| otherwise = paso ys (y:zzs)

paso _ zs = reverse zs

Responder

reducida :: [Int] -> [Int]
reducida xs |ultimaRed xs    = xs
            |otherwise       = reducida (reducir xs)

ultimaRed :: [Int] -> Bool
ultimaRed xs = (reducir xs) == xs
  
reducir :: [Int] -> [Int]
reducir [] = []
reducir (x:[]) = [x]
reducir (x:y:xs) |x == -y        = reducida xs
                  |otherwise      = x:(reducida (y:xs))

reducida :: [Int] -> [Int]

reducida xs |ultimaRed xs = xs

|otherwise = reducida (reducir xs)

ultimaRed :: [Int] -> Bool

ultimaRed xs = (reducir xs) == xs

reducir :: [Int] -> [Int]

reducir [] = []

reducir (x:[]) = [x]

reducir (x:y:xs) |x == -y = reducida xs

|otherwise = x:(reducida (y:xs))

Responder

Reducción de opuestos

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico