Acrónimos
Introducción
A partir de una palabra de puede formar un acrónimo uniendo un prefijo de la primera con un sufijo de la segunda. Por ejemplo,
- «ofimática» es un acrónimo de «oficina» e «informática»
- «informática» es un acrónimo de «información» y «automática»
- «teleñeco» es un acrónimo de «televisión» y «muñeco»
Enunciado
|
1 2 3 4 5 6 |
-- Definir la función -- esAcronimo :: String -> String -> String -> Bool -- tal que (esAcronimo xs ys zs) se verifica si xs es un acrónimo de ys -- y zs. Por ejemplo, -- esAcronimo "ofimatica" "oficina" "informatica" == True -- esAcronimo "informatica" "informacion" "automatica" == True |
|
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 45 46 47 48 49 50 51 52 |
import Data.List import Test.QuickCheck -- 1ª definición -- ============= esAcronimo1 :: String -> String -> String -> Bool esAcronimo1 xs ys zs = xs `elem` acronimos ys zs -- (acronimos xs ys) es la lista de acrónimos de xs e ys. Por ejemplo, -- ghci> acronimos "ab" "cde" -- ["cde","de","e","","acde","ade","ae","a","abcde","abde","abe","ab"] acronimos :: String -> String -> [String] acronimos xs ys = [us++vs | us <- inits xs, vs <- tails ys] -- 2ª definición -- ============= esAcronimo2 :: String -> String -> String -> Bool esAcronimo2 xs ys zs = or [isPrefixOf us ys && isSuffixOf vs zs | (us,vs) <- [splitAt n xs | n <- [0..length xs]]] -- Verificación de equivalencia -- ============================ -- La propiedad es prop_esAcronimo :: String -> String -> String -> Bool prop_esAcronimo xs ys zs = esAcronimo1 xs ys zs == esAcronimo2 xs ys zs -- La comprobación es -- ghci> quickCheck prop_esAcronimo -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- ghci> let r = replicate -- -- ghci> let n = 500 in esAcronimo1 (r n 'a' ++ r n 'b') (r n 'a') (r n 'b') -- True -- (3.76 secs, 1779334696 bytes) -- -- ghci> let n = 500 in esAcronimo2 (r n 'a' ++ r n 'b') (r n 'a') (r n 'b') -- True -- (0.04 secs, 16715376 bytes) -- -- La 2ª definición es más eficiente |