Relación 4 extra 3 Sol

-- 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]
-- ---------------------------------------------------------------------

mezcla :: Ord a => [a] -> [a] -> [a] 
mezcla [] [] = []
mezcla xs [] = xs
mezcla [] ys = ys
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])
-- ---------------------------------------------------------------------

mitades :: [a] -> ([a],[a])
mitades xs = (take n xs, drop n xs)
  where n = length xs `div` 2
             
-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------

ordMezcla :: Ord a => [a] -> [a]
ordMezcla [] = []
ordMezcla [x] = [x]
ordMezcla xs = mezcla (ordMezcla (fst mitad)) (ordMezcla (snd mitad))
  where mitad = 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
-- ---------------------------------------------------------------------

ordenada :: Ord a => [a] -> Bool
ordenada xs = all (\ (x,y) -> x <= y) (zip xs (tail xs))

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

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

-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------

borra :: Eq a => a -> [a] -> [a]
borra y [] = []
borra y (x:xs) | y == x = xs
               | otherwise = x:borra y 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
-- ---------------------------------------------------------------------

esPermutacion :: Eq a => [a] -> [a] -> Bool
esPermutacion [] [] = True
esPermutacion xs [] = False
esPermutacion [] ys = 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.
-- ---------------------------------------------------------------------

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