Menu Close

Eliminaciones anotadas

Definir la función

   eliminaciones :: [a] -> [(a,Int,[a])]

tal que (eliminaciones xs) es la lista de ternas (x,i,zs) tales que x es un elemento de xs, i es la posición de x en xs y zs es la lista de los restantes elementos de xs. Por ejemplo,

   λ> eliminaciones [5,7,6,5]
   [(5,0,[7,6,5]),(7,1,[5,6,5]),(6,2,[5,7,5]),(5,3,[5,7,6])]

Soluciones

import Test.QuickCheck (quickCheck)
 
-- 1ª solución
eliminaciones :: [a] -> [(a,Int,[a])]
eliminaciones xs = [(z,i,zs) | ((z,zs),i) <- zip (aux xs) [0..]]
  where aux []       = []
        aux [x]      = [(x,[])]
        aux (x:y:zs) = (x,y:zs) : [(v,x:vs) | (v,vs) <- aux (y:zs)]
 
-- 2ª solución
eliminaciones2 :: [a] -> [(a,Int,[a])]
eliminaciones2 xs =
  [(v,i,us++vs) | i <- [0..length xs - 1],
                  let (us,v:vs) = splitAt i xs]
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_equivalencia :: [Int] -> Bool
prop_equivalencia xs =
  eliminaciones xs == eliminaciones2 xs
 
-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Ejercicio, Inicial

4 soluciones de “Eliminaciones anotadas

  1. Rubén Muñoz Mkrtchian
    eliminaciones :: [a] -> [(a,Int,[a])]
    eliminaciones xs = [(x,k,borraElemento k xs) | (x,k) <- zip xs [0..]]
     
    -- borraElemento k xs elimina el elemento de xs que se encuentre en la
    -- posición k (entendemos que el primer elemento ocupa la posición 0). Por
    -- ejemplo,
    --   λ> borraElemento 2 [5,7,6,5]
    --   [5,7,5]
     
    borraElemento :: Int -> [a] -> [a]
    borraElemento k xs = take k xs ++ drop (k+1) xs
  2. Mercedes Vega Gallo
    eliminaciones :: [a] -> [(a,Int,[a])]
    eliminaciones xs = map p (zip xs [0..])
                       where p (a,b) = (a,b,remove b xs)
     
    -- La función "remove y xs" elimina de la lista xs el elemento que ocupa la
    -- posición y.
    remove :: Int -> [a] -> [a]
    remove y xs = take y xs ++ drop (y+1) xs
  3. Alejandro García Alcaide
    -- Definiendo varias funciones auxiliares, la funcion eliminaciones xs queda: 
    eliminaciones :: [a] -> [(a,Int,[a])]
    eliminaciones xs = [(x,i,rs) | (x,i,rs) <- zip3 xs [0..] (combinaciones xs)]
     
     
    -- La funcion combinaciones xs da las diferentes listas de xs eliminando un
    -- elemento diferente en cada una de estas. Por ejemplo:
    -- combinaciones [5,7,6,5] == [[7,6,5],[5,6,5],[5,7,5],[5,7,6]]
    -- combinaciones [1,2,3,4] == [[2,3,4],[1,3,4],[1,2,4],[1,2,3]]
     
    combinaciones :: [a] -> [[a]]
    combinaciones xs = [elimina n xs | n <- [1..p]]
     where p = length xs
     
     
    -- La funcion elimina n xs elimina el elemento en la posicion n (siendo el
    -- primer elemento el 1) de la lista xs. Por ejemplo:
    -- elimina 2 [1,2,3]   == [1,3]
    -- elimina 4 [5,7,6,8] == [5,7,6]
     
    elimina :: (Eq t, Num t) => t -> [a] -> [a]
    elimina _ []     = []
    elimina n (x:xs) | n == 1    = xs
                     | otherwise = x: elimina (n-1) xs
  4. Adolfo Enrique Vázquez Ruiz
     
    eliminaciones :: [a] -> [(a,Int,[a])]
    eliminaciones xs = [(a,b,listaSinElemPosic xs b) | (a,b) <- zip xs [0..(length(xs) - 1)]]
     
    -- listaSinElemPosic es una función que, dada una lista y un natural (o cero)
    -- devuelve la lista sin el elemento que se encuentra en la posición indicada
    -- por el natural (tomando como referencia que la posición de head xs es 0). Por
    -- ejemplo,
    --    listaSinElemPosic [1..10] 5 = [1,2,3,4,5,7,8,9,10]
    --    listaSinElemPosic [1,2] 3   = [1,2]
    listaSinElemPosic :: [a] -> Int -> [a]
    listaSinElemPosic xs b = (take b xs) ++ (drop (b+1) xs)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.