Menu Close

Inversa a trozos

José A. Alonso,

Enunciado

-- Definir la función 
--    inversa :: Int -> [a] -> [a]
-- tal que (inversa k xs) es la lista obtenida invirtiendo elementos de
-- xs, k elementos cada vez. Si el número de elementos de xs no es un
-- múltiplo de k, entonces los finales elementos de xs se dejen sin
-- invertir. Por ejemplo,
--    inversa 3 [1..11]  ==  [3,2,1,6,5,4,9,8,7,10,11]
--    inversa 4 [1..11]  ==  [4,3,2,1,8,7,6,5,9,10,11]
--
-- Comprobar con QuickCheck que la función inversa es involutiva; es
-- decir, para todo número k>0 y toda lista xs, se tiene que
-- (inversa k (inversa k xs)) es igual a xs

Soluciones

import Test.QuickCheck
 
-- 1ª definición
inversa1 :: Int -> [a] -> [a]
inversa1 k xs 
    | length xs < k = xs
    | otherwise     = reverse (take k xs) ++ inversa1 k (drop k xs) 
 
-- 2ª definición 
inversa2 :: Int -> [a] -> [a]
inversa2 k xs = aux xs (length xs) where
    aux xs n
        | n < k     = xs
        | otherwise = reverse (take k xs) ++ aux (drop k xs) (n-k)
 
 
-- La dos definiciones son equivalentes
prop_equivalencia ::Int -> [Int] -> Property
prop_equivalencia k xs =
    k > 0 ==> inversa1 k xs == inversa2 k xs
 
-- La comprobación es
--    ghci> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.
 
-- La segunda es más eficiente
--    ghci> :set +s 
--    
--    ghci> last (inversa1 3 [1..100000])
--    100000
--    (16.42 secs, 17576420 bytes)
--     
--    ghci> last (inversa2 3 [1..100000])
--    100000
--    (0.11 secs, 18171356 bytes)
 
-- La propiedad es 
prop_inversa :: Int -> [Int] -> Property
prop_inversa k xs =
    k > 0 ==> inversa2 k (inversa2 k xs) == xs
 
-- La comprobación es 
--    ghci> quickCheck prop_inversa
--    +++ OK, passed 100 tests.
Medio
, , , , ,

2 soluciones de “Inversa a trozos”

  1. Responder
    Jesús Navas Orozco 
    inversa :: Int -> [a] -> [a]
inversa k xs 
    | length xs < k  = xs
    | otherwise      = reverse (take k xs) ++ inversa k (drop k xs)
 
prop_inversa :: Eq a => Int -> [a] -> Property
prop_inversa k xs = k > 0 ==> inversa k (inversa k xs) == xs
 
-- La comprobación es:
--    *Main> quickCheck prop_inversa
--    +++ OK, passed 100 tests
  2. Responder
    Pedro Martín Chávez 
    inversa :: Int -> [a] -> [a]
inversa _ [] = []
inversa k xs
    | mod l k == 0 = reverse (take k xs) ++ inversa k (drop k xs)
    | otherwise    = inversa k (take n xs) ++ drop n xs
    where l = length xs
          n = l - mod l k
 
-- La propiedad es:
prop_inversa :: Eq a => Int -> [a] -> Property
prop_inversa k xs = k > 0 ==> xs == inversa k (inversa k xs)
 
-- La comprobación es:
-- *Main> quickCheck prop_inversa
-- +++ OK, passed 100 tests.

Escribe tu solución

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