Relación 4 extra 3

-- Definiciones por recursión: Ordenación por mezcla.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- El objetivo de esta relación es definir la ordenación por mezclas y
-- comprobar su corrección con QuickCheck.

import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir por recursión la función
--    mezcla :: Ord a => [a] -> [a] -> [a] 
-- tal que (mezcla xs ys) es la lista obtenida mezclando las listas
-- ordenadas xs e ys. Por ejemplo,  
--    mezcla [2,5,6] [1,3,4]  ==  [1,2,3,4,5,6]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla xs [] = xs
mezcla [] xs = xs
mezcla (x:xs) (y:ys) | x < y =  x:(mezcla xs (y:ys))
                     | otherwise = y:(mezcla (x:xs) ys)

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función 
--    mitades :: [a] -> ([a],[a]) 
-- tal que (mitades xs) es el par formado por las dos mitades en que se
-- divide xs tales que sus longitudes difieren como máximo en uno. Por
-- ejemplo, 
--    mitades [2,3,5,7,9]  ==  ([2,3],[5,7,9])
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

mitades :: [a] -> ([a],[a]) 
mitades xs = splitAt (div (length xs) 2) xs

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir por recursión la función 
--    ordMezcla :: Ord a => [a] -> [a]
-- tal que (ordMezcla xs) es la lista obtenida ordenado xs por mezcla
-- (es decir, considerando que la lista vacía y las listas unitarias
-- están ordenadas y cualquier otra lista se ordena mezclando las dos
-- listas que resultan de ordenar sus dos mitades por separado). Por
-- ejemplo, 
--    ordMezcla [5,2,3,1,7,2,5]  ==  [1,2,2,3,5,5,7]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

ordMezcla :: Ord a => [a] -> [a]
ordMezcla [] = []
ordMezcla [x] = [x]
ordMezcla xs = mezcla (ordMezcla (fst m)) ((ordMezcla (snd m)))
          where m = mitades xs
          
-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir por recursión la función
--    ordenada :: Ord a => [a] -> Bool
-- tal que (ordenada xs) se verifica si xs es una lista ordenada. Por
-- ejemplo, 
--    ordenada [2,3,5]  ==  True
--    ordenada [2,5,3]  ==  False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

ordenada :: Ord a => [a] -> Bool
ordenada [] = True
ordenada [_] = True
ordenada (x:xs) = x <= (head xs) && ordenada xs

-- ---------------------------------------------------------------------
-- Ejercicio 5. Comprobar con QuickCheck que la ordenación por mezcla
-- de una lista es una lista ordenada.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

-- La propiedad es
prop_ordMezcla_ordenada :: [Int] -> Bool
prop_ordMezcla_ordenada xs = ordenada (ordMezcla xs)

-- La comprobación es
-- *Main> quickCheck prop_ordMezcla_ordenada
-- +++ OK, passed 100 tests.
    
-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir por recursión la función
--    borra :: Eq a => a -> [a] -> [a]
-- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de
-- x en la lista xs. Por ejemplo, 
--    borra 1 [1,2,1]  ==  [2,1]
--    borra 3 [1,2,1]  ==  [1,2,1]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

borra :: Eq a => a -> [a] -> [a]
borra n [] = []
borra n (x:xs) = if n /= x then x:(borra n xs) else xs

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir por recursión la función 
--    esPermutacion :: Eq a => [a] -> [a] -> Bool
-- tal que (esPermutacion xs ys) se verifica si xs es una permutación de
-- ys. Por ejemplo, 
--    esPermutacion [1,2,1] [2,1,1]  ==  True
--    esPermutacion [1,2,1] [1,2,2]  ==  False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

esPermutacion :: Eq a => [a] -> [a] -> Bool
esPermutacion [] [] = True
esPermutacion [x] [] = False
esPermutacion [] [x] = False
esPermutacion (x:xs) (y:ys) = esPermutacion xs (borra x (y:ys)) 

-- ---------------------------------------------------------------------
-- Ejercicio 8. Comprobar con QuickCheck que la ordenación por mezcla
-- de una lista es una permutación de la lista.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

-- La propiedad es
prop_ordMezcla_pemutacion :: [Int] -> Bool
prop_ordMezcla_pemutacion xs = esPermutacion xs (ordMezcla xs) 

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