Inversa a trozos
Enunciado
|
1 2 3 4 5 6 7 8 9 10 11 12 |
-- 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
[schedule expon=’2014-11-27′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 27 de noviembre.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2014-11-27′ at=»06:00″]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
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. |
[/schedule]