-- I1M 2009-10: G1_Rel_10.hs
-- 10ª relación de ejercicios (11 de Diciembre)
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

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

import Data.Char
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1. Redefinir, usando foldr, la función maximum.
-- ---------------------------------------------------------------------

maximum' :: (Ord a) => [a] -> a
maximum' (x:xs) = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 2. Redefinir, usando foldr, la función minimum.
-- ---------------------------------------------------------------------

minimum' :: (Ord a) => [a] -> a
minimum' (x:xs) = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir, usando foldr, la función
--    inversaFR :: [a] -> [a]
-- tal que (inversaFR xs) es la inversa de la lista xs. Por ejemplo,
--    inversaFR [3,5,2,4,7]  =>  [7,4,2,5,3]
-- ---------------------------------------------------------------------

inversaFR :: [a] -> [a]
inversaFR = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir, usando foldl, la función
--    inversaFL :: [a] -> [a]
-- tal que (inversaFL xs) es la inversa de la lista xs. Por ejemplo,
--    inversaFL [3,5,2,4,7]  =>  [7,4,2,5,3]
-- ---------------------------------------------------------------------

inversaFL :: [a] -> [a]
inversaFL = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 5. Comprobar con QuickCheck que las funciones reverse,
-- inversaFR e inversaFL son equivalentes.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_inversa :: Eq a => [a] -> Bool
prop_inversa xs = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 6. Comparar la eficiencia de inversaFR e inversaFL
-- calculando el tiempo y el espacio que usado en evaluar las siguientes
-- expresiones: 
--    head (inversaFR [1..100000])
--    head (inversaFL [1..100000])
-- ---------------------------------------------------------------------

-- La sesión es

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir, la función
--    dec2ent :: [Int] -> Int
-- tal que (dec2ent xs) es el entero correspondiente a la expresión
-- decimal xs. Por ejemplo,
--    dec2ent [2,3,4,5]  =>  2345
-- Escribir dos definiciones:
-- * dec2entR por recursión
-- * dec2entF usando foldl
-- ---------------------------------------------------------------------

-- La definición por recursión es
dec2entR :: [Int] -> Int
dec2entR = undefined

-- La definición usando foldl es
dec2entF :: [Int] -> Int
dec2entF = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir, mediante plegado, la función
--    sumll :: Num a => [[a]] -> a
-- tal que (sumll xss) es la suma de las sumas de las listas de xss. Por
-- ejemplo, 
--    sumll [[1,3],[2,5]]  =>  11
-- ---------------------------------------------------------------------

sumll :: Num a => [[a]] -> a
sumll = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir, mediante plegado, la función
--    borra :: Eq a => [a] -> a -> [a]
-- tal que (borra xs y) es la lista obtenida borrando la primera
-- ocurrencia de y en xs. Por ejemplo,
--    borra [2,3,5,6] 5    =>  [2,3,6]
--    borra [2,3,5,6,5] 5  =>  [2,3,6,5]
--    borra [2,3,5,6,5] 7  =>  [2,3,5,6,5]
-- ---------------------------------------------------------------------

borra :: Eq a => [a] -> a -> [a]
borra xs y = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir, mediante plegado, la función
--    diferencia :: Eq a => [a] -> [a] -> [a]
-- tal que (diferencia xs ys) es la diferencia del conjunto xs e ys; es
-- decir el conjunto de los elementos de xs que no pertenecen a ys. Por
-- ejemplo,  
--    diferencia [2,3,5,6] [5,2,7]  =>  [3,6]
-- ---------------------------------------------------------------------

diferencia :: Eq a => [a] -> [a] -> [a]
diferencia = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 11. En el tema se ha definido la función
--    composicionLista :: [a -> a] -> (a -> a)
-- tal que (composicionLista fs) es la composición de la lista de
-- funciones fs. Por ejemplo,
--    composicionLista [(*2),(^2)] 3                18
--    composicionLista [(^2),(*2)] 3                36
--    composicionLista [(/9),(^2),(*2)] 3           4.0
-- La definición es
--    composicionLista = foldr (.) id
-- 
-- Explicar por qué la siguiente definición no es válida: 
--    sumaCuadradosPares = 
--        composicionLista [sum, map (^2), filter even]
-- ---------------------------------------------------------------------

-- La razón es ...

-- ---------------------------------------------------------------------
-- Ejercicio 12. Se define el siguiente patrón
--    unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
--    unfold p h t x | p x       = []
--                   | otherwise = h x : unfold p h t (t x)
-- Con el patrón unfold pueden simplificarse algunas definiciones. Por
-- ejemplo, en el tema se ha definido la función 
--    int2bin :: Int -> [Int]
-- tal que (int2bin x) es el número binario correspondiente al número
-- decimal x. Por ejemplo,
--    int2bin 13  =>  [1,0,1,1]
-- La definición en el tema es
--    int2bin 0 = []
--    int2bin n = n `mod` 2 : int2bin (n `div` 2)
-- Usando unfold, int2bin puede definirse como
--    int2bin = unfold (== 0) (`mod` 2) (`div` 2)
-- ---------------------------------------------------------------------

unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
unfold p h t x = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 13. Redefinir, usando unfold, la función definida en el
-- tema 
--    separaOctetos :: [Int] -> [[Int]]
-- tal que (separaOctetos bs) es la lista obtenida separando la lista de
-- bits bs en listas de 8 elementos. Por ejemplo,
--    *Main> separaOctetos [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0]
--    [[1,0,0,0,0,1,1,0],[0,1,0,0,0,1,1,0]]
-- Comprobar con quickCheck la equivalencia de las definiciones.
-- ---------------------------------------------------------------------

-- La definición en el tema es
separaOctetos :: [Int] -> [[Int]]
separaOctetos [] = []
separaOctetos bs = take 8 bs : separaOctetos (drop 8 bs)

-- La definición con unfold es
separaOctetos' :: [Int] -> [[Int]]
separaOctetos' = undefined

-- La propiedad es
prop_separaOctetos xs = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 14. Redefinir, usando unfold, la función map. 
-- ---------------------------------------------------------------------

-- La definición es
map'' :: (a -> b) -> [a] -> [b]
map'' f = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 15. En este ejercicio se va a modificar el programa de
-- transmisión de cadenas para detectar errores de transmisión sencillos
-- usando bits de paridad. Es decir, cada octeto de ceros y unos
-- generado durante la codificación se extiende con un bit de paridad
-- que será un uno si el número contiene un número impar de unos y cero
-- en caso contrario. En la decodificación, en cada número binario de 9
-- cifras debe comprobarse que la paridad es correcta, en cuyo caso se
-- descarta el bit de paridad. En caso contrario, debe generarse un
-- mensaje de error en la paridad. 
-- 
-- Se usarán las siguientes definiciones del tema
-- ---------------------------------------------------------------------

type Bit = Int  

bin2int :: [Bit] -> Int
bin2int =  foldr (\x y -> x + 2*y) 0

int2bin :: Int -> [Bit]
int2bin 0 =  []
int2bin n =  n `mod` 2 : int2bin (n `div` 2)

creaOcteto :: [Bit] -> [Bit]
creaOcteto bs =  take 8 (bs ++ repeat 0)

-- ---------------------------------------------------------------------
-- Ejercicio 16. Definir la función
--    paridad :: [Bit] -> Bit
-- tal que (paridad bs) es el bit de paridad de bs; es decir, 1 si bs
-- contiene un número impar de unos y 0 en caso contrario. Por ejemplo, 
--    paridad [0,1,1]      =>  0
--    paridad [0,1,1,0,1]  =>  1
-- ---------------------------------------------------------------------

paridad :: [Bit] -> Bit
paridad bs = undefined
           | otherwise     = 0

-- ---------------------------------------------------------------------
-- Ejercicio 17. Definir la función
--    agregaParidad :: [Bit] -> [Bit]
-- tal que (agregaParidad bs) es la lista obtenida añadiendo al
-- principio de bs su paridad. Por ejemplo,
--    agregaParidad [0,1,1]      =>  [0,0,1,1]
--    agregaParidad [0,1,1,0,1]  =>  [1,0,1,1,0,1]
-- ---------------------------------------------------------------------

agregaParidad :: [Bit] -> [Bit]
agregaParidad bs = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 18. Definir la función
--    codifica :: String -> [Bit]
-- tal que (codifica c) es la codificación de la cadena c como una lista
-- de bits obtenida convirtiendo cada carácter en un número Unicode,
-- convirtiendo cada uno de dichos números en un octeto con su paridad y
-- concatenando los octetos con paridad para obtener una lista de
-- bits. Por ejemplo, 
--    *Main> codifica "abc"
--    [1,1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0]
-- ---------------------------------------------------------------------

codifica :: String -> [Bit]
codifica = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 19. Definir la función
--    separa9 :: [Bit] -> [[Bit]]
-- tal que (separa9 bs)} es la lista obtenida separando la lista de bits
-- bs en listas de 9 elementos. Por ejemplo, 
--    *Main> separa9 [1,1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0]
--    [[1,1,0,0,0,0,1,1,0],[1,0,1,0,0,0,1,1,0],[0,1,1,0,0,0,1,1,0]]
-- ---------------------------------------------------------------------

separa9 :: [Bit] -> [[Bit]]
separa9 = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 20. Definir la función
--    compruebaParidad :: [Bit] -> [Bit ]
-- tal que (compruebaParidad bs) es el resto de bs si el primer elemento
-- de bs es el bit de paridad del resto de bs y devuelve error de
-- paridad en cao contrario. Por ejemplo,
--    *Main> compruebaParidad [1,1,0,0,0,0,1,1,0]
--    [1,0,0,0,0,1,1,0]
--    *Main> compruebaParidad [0,1,0,0,0,0,1,1,0]
--    *** Exception: paridad erronea
-- Usar la función del preludio
--    error :: String -> a
-- tal que (error c) devuelve la cadena c.
-- ---------------------------------------------------------------------

compruebaParidad :: [Bit] -> [Bit ]
compruebaParidad (b:bs) = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 21. Definir la función
--    descodifica :: [Bit] -> String
-- tal que (descodifica bs) es la cadena correspondiente a la lista de
-- bits con paridad. Para ello, en cada número binario de 9 cifras debe
-- comprobarse que la paridad es correcta, en cuyo caso se descarta el
-- bit de paridad. En caso contrario, debe generarse un mensaje de error
-- en la paridad. Por ejemplo,   
--    descodifica [1,1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0]
--    =>  "abc"
--    descodifica [1,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0]
--    =>  "*** Exception: paridad erronea
-- ---------------------------------------------------------------------
   
descodifica :: [Bit] -> String
descodifica = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 22. Se define la función
transmite :: ([Bit] -> [Bit]) -> String -> String
transmite canal =  descodifica . canal . codifica
-- tal que (transmite c t) es la cadena obtenida transmitiendo la cadena
-- t a través del canal c. Calcular el resultado de transmitir la cadena
-- "Conocete a ti mismo" por el canal identidad (id) y del canal que
-- olvida el primer bit (tail).
-- ---------------------------------------------------------------------

-- El resultado es