Relación 8

-- I1M 2021-22
-- Funciones sobre cadenas.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Data.Char
import Data.List
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir, por comprensión, la función
--    sumaDigitosC :: String -> Int
-- tal que (sumaDigitosC xs) es la suma de los dígitos de la cadena
-- xs. Por ejemplo,
--    sumaDigitosC "SE 2431 X"  ==  10
-- Nota: Usar las funciones (isDigit c) que se verifica si el carácter c
-- es un dígito y (digitToInt d) que es el entero correspondiente al
-- dígito d.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaDigitosC :: String -> Int
sumaDigitosC xs = sum [digitToInt x | x <- xs, isDigit x]

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir, por recursión, la función
--    sumaDigitosR :: String -> Int
-- tal que (sumaDigitosR xs) es la suma de los dígitos de la cadena
-- xs. Por ejemplo,
--    sumaDigitosR "SE 2431 X"  ==  10
-- Nota: Usar las funciones isDigit y digitToInt.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaDigitosR :: String -> Int
sumaDigitosR [] = 0 
sumaDigitosR (x:xs) = if isDigit x then digitToInt x + sumaDigitosR xs else sumaDigitosR xs


-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Definir, por orden superior, la función
--    sumaDigitosMF :: String -> Int
-- tal que (sumaDigitosMF xs) es la suma de los dígitos de la cadena
-- xs. Por ejemplo,sumaDigitosR [] = 0 
--    sumaDigitosMF "SE 2431 X"  ==  10
-- Nota: Usar las funciones isDigit y digitToInt.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaDigitosMF :: String -> Int
sumaDigitosMF [] = 0
sumaDigitosMF xs = sum (map digitToInt (filter isDigit xs))

-- ---------------------------------------------------------------------
-- Ejercicio 1.4. Comprobar con QuickCheck que las definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_sumaDigitos :: String -> Bool
prop_sumaDigitos xs = sumaDigitosR xs == sumaDigitosC xs && sumaDigitosC xs == sumaDigitosMF xs && sumaDigitosR xs == sumaDigitosMF xs

-- La comprobación es
-- *Main> quickCheck prop_sumaDigitos
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Definir, por comprensión, la función
--    mayusculaInicial :: String -> String
-- tal que (mayusculaInicial xs) es la palabra xs con la letra inicial
-- en mayúscula y las restantes en minúsculas. Por ejemplo,
--    mayusculaInicial "sEviLLa"  ==  "Sevilla"
--    mayusculaInicial ""         ==  ""
-- Nota: Usar las funciones (toLower c) que es el carácter c en
-- minúscula y (toUpper c) que es el carácter c en mayúscula.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
mayusculaInicial :: String -> String
mayusculaInicial [] = ""
mayusculaInicial xs = [toUpper (head xs)] ++ [toLower x | x <- (tail xs) ]

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir, por recursión, la función
--    mayusculaInicialRec :: String -> String
-- tal que (mayusculaInicialRec xs) es la palabra xs con la letra
-- inicial en mayúscula y las restantes en minúsculas. Por ejemplo,
--    mayusculaInicialRec "sEviLLa"  ==  "Sevilla"
--    mayusculaInicialRec "s"        ==  "S"
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
mayusculaInicialRec :: String -> String
mayusculaInicialRec [] = ""
mayusculaInicialRec (x:xs) = [toUpper x] ++ mayusculaInicialRec' xs

mayusculaInicialRec' :: String -> String
mayusculaInicialRec' [] = ""
mayusculaInicialRec' (x:xs) = [toLower x] ++ mayusculaInicialRec' xs

-- ---------------------------------------------------------------------
-- Ejercicio 2.3. Definir, por orden superior, la función
--    mayusculaInicialMF :: String -> String
-- tal que (mayusculaInicialMF xs) es la palabra xs con la letra
-- inicial en mayúscula y las restantes en minúsculas. Por ejemplo,
--    mayusculaInicialMF "sEviLLa"  ==  "Sevilla"
--    mayusculaInicialMF "s"        ==  "S"
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
mayusculaInicialMF :: String -> String
mayusculaInicialMF [] = ""
mayusculaInicialMF (x:xs) = [toUpper x] ++ map toLower (xs)

-- -------------------------------------------------------------------
-- Ejercicio 2.4. Comprobar con QuickCheck que las definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_mayusculaInicial :: String -> Bool
prop_mayusculaInicial xs = mayusculaInicial xs == mayusculaInicialRec xs && mayusculaInicial xs == mayusculaInicialMF xs && mayusculaInicialRec xs == mayusculaInicialMF xs

-- La comprobación es
-- *Main> quickCheck prop_mayusculaInicial
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Se consideran las siguientes reglas de mayúsculas
-- iniciales para los títulos:
--    * la primera palabra comienza en mayúscula y
--    * todas las palabras que tienen 4 letras como mínimo empiezan
--      con mayúsculas
-- Definir, por comprensión, la función
--    titulo :: [String] -> [String]
-- tal que (titulo ps) es la lista de las palabras de ps con
-- las reglas de mayúsculas iniciales de los títulos. Por ejemplo,
--    ghci> titulo ["eL","arTE","DE","La","proGraMacion"]
--    ["El","Arte","de","la","Programacion"]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
titulo :: [String] -> [String]
titulo [] = []
titulo (x:xs) = [mayusculaInicial x] ++ [inicialPalabra y | y <- [mayusculaInicial p | p <- xs]]

inicialPalabra :: String -> String
inicialPalabra [] = ""
inicialPalabra (y:ys) | length (y:ys) < 4 = [toLower y] ++ ys
                      | otherwise = (y:ys)
                      
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Definir, por recursión, la función
--    tituloRec :: [String] -> [String]
-- tal que (tituloRec ps) es la lista de las palabras de ps con
-- las reglas de mayúsculas iniciales de los títulos. Por ejemplo,
--    ghci> tituloRec ["eL","arTE","DE","La","proGraMacion"]
--    ["El","Arte","de","la","Programacion"]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
tituloRec :: [String] -> [String]
tituloRec [] = []
tituloRec (x:xs) = [mayusculaInicialRec x] ++ reglasPalabras xs

reglasPalabras :: [String] -> [String]
reglasPalabras [] = []
reglasPalabras (x:xs) | length x >= 4 = [mayusculaInicialRec x] ++ reglasPalabras xs
                      | otherwise = [inicialMinuscula x] ++ reglasPalabras xs

inicialMinuscula :: String -> String
inicialMinuscula [] = ""
inicialMinuscula (x:xs) = [toLower x] ++ inicialMinuscula xs 

-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_titulo :: [String] -> Bool
prop_titulo xs = titulo xs == tituloRec xs

-- La comprobación es
-- *Main> quickCheck prop_titulo
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir, por comprensión, la función
--    posiciones :: String -> Char -> [Int]
-- tal que (posiciones xs y) es la lista de la posiciones del carácter y
-- en la cadena xs. Por ejemplo,
--    posiciones "Salamanca" 'a'  ==  [1,3,5,8]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
posiciones :: String -> Char -> [Int]
posiciones xs y = [p | (x,p) <- zip xs [0..], x == y]

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Definir, por recursión, la función
--    posicionesR :: String -> Char -> [Int]
-- tal que (posicionesR xs y) es la lista de la posiciones del
-- carácter y en la cadena xs. Por ejemplo,
--    posicionesR "Salamanca" 'a'  ==  [1,3,5,8]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
posicionesR :: String -> Char -> [Int]
posicionesR [] _ = [] 
posicionesR xs y = posicionesRAux xs y 0 

posicionesRAux :: String -> Char -> Int -> [Int]
posicionesRAux [] _ _ = [] 
posicionesRAux (x:xs) y n = if x == y then [n] ++ posicionesRAux xs y (n+1)
                               else posicionesRAux xs y (n+1) 
           

-- ---------------------------------------------------------------------
-- Ejercicio 4.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_posiciones :: String -> Char -> Bool
prop_posiciones xs y = posiciones xs y == posicionesR xs y 

-- La comprobación es
-- *Main> quickCheck prop_posiciones 
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 5.1. Definir, por recursión, la función
--    contieneR :: String -> String -> Bool
-- tal que (contieneR xs ys) se verifica si ys es una subcadena de
-- xs. Por ejemplo,
--    contieneR "escasamente" "casa"   ==  True
--    contieneR "escasamente" "cante"  ==  False
--    contieneR "" ""                  ==  True
-- Nota: Se puede usar la predefinida (isPrefixOf ys xs) que se verifica
-- si ys es un prefijo de xs.
-- --------------------------------------------------------------------- 

-- Álvaro Galisteo:
contieneR :: String -> String -> Bool
contieneR [] x = if x == [] then True else False
contieneR (x:xs) ys = if not (isPrefixOf ys (x:xs)) then contieneR xs ys 
                      else True
                    

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Definir, por comprensión, la función
--    contieneC :: String -> String -> Bool
-- tal que (contiene xs ys) se verifica si ys es una subcadena de
-- xs. Por ejemplo,
--    contieneC "escasamente" "casa"      ==  True
--    contieneC "escasamente" "cante"     ==  False
--    contieneC "casado y casada" "casa"  ==  True
--    contieneC "" ""                     ==  True
-- Nota: Se puede usar la predefinida (isPrefixOf ys xs) que se verifica
-- si ys es un prefijo de xs.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
contieneC :: String -> String -> Bool
contieneC [] x = if x == [] then True else False
contieneC xs ys = or [ isPrefixOf ys x | x <-[reverse y | y <- inits (reverse xs)]] 

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Definir, por orden superior, la función
--    contiene :: String -> String -> Bool
-- tal que (contiene xs ys) se verifica si ys es una subcadena de
-- xs. Por ejemplo,
--    contiene "escasamente" "casa"      ==  True
--    contiene "escasamente" "cante"     ==  False
--    contiene "casado y casada" "casa"  ==  True
--    contiene "" ""                     ==  True
-- Nota: Se puede usar la predefinida (isPrefixOf ys xs) que se verifica
-- si ys es un prefijo de xs.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
contiene :: String -> String -> Bool
contiene xs ys = or (map (isPrefixOf ys) (map reverse (inits (reverse xs))))

-- ---------------------------------------------------------------------
-- Ejercicio 5.3. Comprobar con QuickCheck que las definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_contiene :: String -> String -> Bool
prop_contiene xs ys = contieneR xs ys == contieneC xs ys && contieneR xs ys == contiene xs ys && contiene xs ys == contieneC xs ys 

-- La comprobación es
-- *Main> quickCheck prop_contiene
-- +++ OK, passed 100 tests.