Ir al contenido principal

Acrónimos

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"

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

Soluciones

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,
--    λ> 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
--    λ> quickCheck prop_esAcronimo
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> let r = replicate
--
--    λ> let n = 500 in esAcronimo1 (r n 'a' ++ r n 'b') (r n 'a') (r n 'b')
--    True
--    (3.76 secs, 1779334696 bytes)
--
--    λ> 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