Compactación de listas

PorJosé A. Alonso 11-febrero-201626-marzo-2022

Definir la función

   compactada :: [Maybe Int] -> [Int]

1	compactada :: [Maybe Int] -> [Int]

tal que (compacta xs) es la lista obtenida al compactar xs con las siguientes reglas:

se eliminan los elementos Nothing;
si dos elementos consecutivos tienen el mismo valor, se sustituyen por el sucesor de su valor y
los restantes elementos no se cambian.

Por ejemplo,

    λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]
    [2,5,3,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]
    [2,1,4,3,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]
    [2,1,5,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]
    [2,1,4,3,4]
    λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]
    [2,2,4,3,4]

λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]

[2,5,3,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]

[2,1,4,3,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]

[2,1,5,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]

[2,1,4,3,4]

λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]

[2,2,4,3,4]

Soluciones

-- 1ª definición
compactada1 :: [Maybe Int] -> [Int]
compactada1 xs = aux (valores xs)
    where aux (x:y:xs) | x == y    = x+1 : aux xs
                       | otherwise = x : aux (y:xs)
          aux xs                   = xs

-- (valores vs) es la lista de los valores de vs. Por ejemplo,
--    ghci> valores [Just 1,Nothing,Just 1,Nothing,Just 3,Just 6]
--    [1,1,3,6]
valores :: [Maybe Int] -> [Int]
valores xs = [x | Just x <- xs]

-- 2ª definición de valores (por recursión):
valores2 :: [Maybe Int] -> [Int]
valores2 []            = []
valores2 ((Just v):vs) = v: valores2 vs
valores2 (Nothing:vs)  = valores2 vs

-- 1ª definición

compactada1 :: [Maybe Int] -> [Int]

compactada1 xs = aux (valores xs)

where aux (x:y:xs) | x == y = x+1 : aux xs

| otherwise = x : aux (y:xs)

aux xs = xs

-- (valores vs) es la lista de los valores de vs. Por ejemplo,

-- ghci> valores [Just 1,Nothing,Just 1,Nothing,Just 3,Just 6]

-- [1,1,3,6]

valores :: [Maybe Int] -> [Int]

valores xs = [x | Just x <- xs]

-- 2ª definición de valores (por recursión):

valores2 :: [Maybe Int] -> [Int]

valores2 [] = []

valores2 ((Just v):vs) = v: valores2 vs

valores2 (Nothing:vs) = valores2 vs

11 Comentarios

import Data.Maybe (catMaybes)

compactada :: [Maybe Int] -> [Int]
compactada = aux . catMaybes
    where aux []  = []
          aux [x] = [x]
          aux (x:y:xs) | x == y    = aux (succ x : xs)
                       | otherwise = x : aux (y:xs)

import Data.Maybe (catMaybes)

compactada :: [Maybe Int] -> [Int]

compactada = aux . catMaybes

where aux [] = []

aux [x] = [x]

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

| otherwise = x : aux (y:xs)

Responder

carruirui3 dice:

12-febrero-2016 a las 10:04

Si aplicas aux a la lista completa, se colapsa en casos como el siguiente, lo que no parece la intención de la función:

Haskell

ejLista = map Just [1,1,2,3,4]

1

ejLista = map Just [1,1,2,3,4]

Los únicos números iguales son 1 y 1. Podría interpretarse que el resultado deseado es [2,2,3,4]. Sin embargo, tu función colapsa todos los valores y devuelve [5]. Habría sido de ayuda un ejemplo similar a este para que se observe dónde deberíamos aplicar la función.

Responder
1. Chema Cortés dice:
  
  15-febrero-2016 a las 13:55
  
  Mi interpreción es que las reglas son aplicables mientras sea posible. Tienes razón que sólo se tiene que hacer la primera sustitución, tal y como muestra el último ejemplo:
  
  λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4] [2,2,4,3,4]
  
  1
  2
  
  λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]
  [2,2,4,3,4]
  
  Por tanto mi solución no es correcta.
  
  Responder

compactada :: [Maybe Int] -> [Int]
compactada xs = valor $ elimina xs
                where elimina [] = []
                      elimina (x:xs) | x == Nothing = elimina xs
                                     | otherwise = x : elimina xs
                      valor [] = []
                      valor [Just x] = [x]
                      valor (Just x:Just y:xs) | x == y = (x+1) : valor xs
                                               | otherwise = x : valor (Just y:xs)

compactada :: [Maybe Int] -> [Int]

compactada xs = valor $ elimina xs

where elimina [] = []

elimina (x:xs) | x == Nothing = elimina xs

| otherwise = x : elimina xs

valor [] = []

valor [Just x] = [x]

valor (Just x:Just y:xs) | x == y = (x+1) : valor xs

| otherwise = x : valor (Just y:xs)

Responder

compactada :: [Maybe Int] -> [Int]
compactada xs = valor $  filter (/= Nothing) xs
    where  valor [] = []
           valor [Just x] = [x]
           valor (Just x:Just y:xs) | x == y = (x+1) : valor xs
                                    | otherwise = x : valor (Just y:xs)

compactada :: [Maybe Int] -> [Int]

compactada xs = valor $ filter (/= Nothing) xs

where valor [] = []

valor [Just x] = [x]

valor (Just x:Just y:xs) | x == y = (x+1) : valor xs

| otherwise = x : valor (Just y:xs)

Responder

import Data.List

compactada :: [Maybe Int] -> [Int]
compactada xs = concat (map f $ group [x | Just x <- xs])
      where f xs | m == 1    = xs
                 | even m    = ys 
                 | otherwise = ys ++ [head xs]
                     where m  = length xs
                           ys = replicate (div m 2) (head xs+1)

import Data.List

compactada :: [Maybe Int] -> [Int]

compactada xs = concat (map f $ group [x | Just x <- xs])

where f xs | m == 1 = xs

| even m = ys

| otherwise = ys ++ [head xs]

where m = length xs

ys = replicate (div m 2) (head xs+1)

Responder

import Data.List

compactada :: [Maybe Int] -> [Int]
compactada = map sig . split . group . map noJust . filter (/= Nothing)
  where noJust :: Maybe a -> a
        noJust (Just a) = a
        split :: [[a]] -> [[a]]
        split [] = []
        split ([]:xss) = split xss
        split ((x:[]):xss) = [x]: split xss
        split ((x:y:xs):xss) = [x,y]: split (xs:xss)
        sig :: Num a => [a] -> a
        sig (x:[])   = x
        sig (x:_:[]) = x+1

import Data.List

compactada :: [Maybe Int] -> [Int]

compactada = map sig . split . group . map noJust . filter (/= Nothing)

where noJust :: Maybe a -> a

noJust (Just a) = a

split :: [[a]] -> [[a]]

split [] = []

split ([]:xss) = split xss

split ((x:[]):xss) = [x]: split xss

split ((x:y:xs):xss) = [x,y]: split (xs:xss)

sig :: Num a => [a] -> a

sig (x:[]) = x

sig (x:_:[]) = x+1

Responder

compactada :: [Maybe Int] -> [Int]
compactada = aux . catMaybes
             where aux xs | length xs < 2      = xs
                          | head xs == (xs!!1) = succ (head xs) : aux (drop 2 xs)
                          | otherwise          = head xs : aux (tail xs)

compactada :: [Maybe Int] -> [Int]

compactada = aux . catMaybes

where aux xs | length xs < 2 = xs

| head xs == (xs!!1) = succ (head xs) : aux (drop 2 xs)

| otherwise = head xs : aux (tail xs)

Responder

compactada :: [Maybe Int] -> [Int]
compactada = compacto . filter (/= Nothing)
             where compacto [] = []
                   compacto [Just x] = [x]
                   compacto (Just x:Just y:xs) | x == y = (x+1) : compacto xs
                                               | otherwise = x : compacto (Just y : xs)

compactada :: [Maybe Int] -> [Int]

compactada = compacto . filter (/= Nothing)

where compacto [] = []

compacto [Just x] = [x]

compacto (Just x:Just y:xs) | x == y = (x+1) : compacto xs

| otherwise = x : compacto (Just y : xs)

Responder

compactada :: [Maybe Int] -> [Int]
compactada [] = []
compactada xs = compacta (group2 (quitaMaybe xs))
 
group2 :: [Int] -> [[Int]]
group2 [] = []
group2 [a] = [[a]]
group2 (x:y:xs) | x == y    = [x,y] : group2 xs
                | otherwise = [x] : group2 (y:xs)          
 
quitaMaybe :: [Maybe Int] -> [Int]
quitaMaybe []            = []
quitaMaybe ((Just a):xs) = a : quitaMaybe xs
quitaMaybe (Nothing:xs)  =  quitaMaybe xs
 
compacta :: [[Int]] -> [Int]
compacta [] = []
compacta (x:xs) | length x == 1 = (head x) : compacta xs
                | otherwise = (head x)+1 : compacta xs

compactada :: [Maybe Int] -> [Int]

compactada [] = []

compactada xs = compacta (group2 (quitaMaybe xs))

group2 :: [Int] -> [[Int]]

group2 [] = []

group2 [a] = [[a]]

group2 (x:y:xs) | x == y = [x,y] : group2 xs

| otherwise = [x] : group2 (y:xs)

quitaMaybe :: [Maybe Int] -> [Int]

quitaMaybe [] = []

quitaMaybe ((Just a):xs) = a : quitaMaybe xs

quitaMaybe (Nothing:xs) = quitaMaybe xs

compacta :: [[Int]] -> [Int]

compacta [] = []

compacta (x:xs) | length x == 1 = (head x) : compacta xs

| otherwise = (head x)+1 : compacta xs

Responder

compactada :: [Maybe Int] -> [Int]
compactada []                              = []
compactada [Just a]                        = [a]
compactada (Nothing:xs)                    = compactada xs
compactada (Just a:Nothing:xs)             = compactada (Just a:xs)
compactada (Just a:Just b:xs) | a==b       = succ a: compactada xs
                              | otherwise  = a : compactada2 (Just b:xs)

compactada :: [Maybe Int] -> [Int]

compactada [] = []

compactada [Just a] = [a]

compactada (Nothing:xs) = compactada xs

compactada (Just a:Nothing:xs) = compactada (Just a:xs)

compactada (Just a:Just b:xs) | a==b = succ a: compactada xs

| otherwise = a : compactada2 (Just b:xs)

Responder

Compactación de listas

Soluciones

11 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

11 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico