Relación 4 extra 4

-- Definiciones por recursión. Tama 6.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

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

-- En esta relación se presentan ejercicios con definiciones por
-- recursión correspondientes al tema 6 
 
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir por recursión la función
--    potencia :: Integer -> Integer -> Integer
-- tal que (potencia x n) es x elevado al número natural n. Por ejemplo,  
--    potencia 2 3  ==  8
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo: 
potencia :: Integer -> Integer -> Integer
potencia m 0 = 1
potencia x n = x*(potencia x (n-1))

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir por recursión la función
--    replicate' :: Int -> a -> [a]
-- tal que (replicate' n x) es la lista formado por n copias del
-- elemento x. Por ejemplo,
--    replicate' 3 2  ==  [2,2,2]
-- ---------------------------------------------------------------------
 
-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
replicate' :: Int -> a -> [a]
replicate' 0 _ = []
replicate' n x = [x] ++ replicate' (n-1) x

-- ---------------------------------------------------------------------
-- Ejercicio 3. Dados dos números naturales, a y b, es posible
-- calcular su máximo común divisor mediante el Algoritmo de
-- Euclides. Este algoritmo se puede resumir en la siguiente fórmula:
--    mcd(a,b) = a,                   si b = 0
--             = mcd (b, a módulo b), si b > 0
-- 
-- Definir la función 
--    mcd :: Integer -> Integer -> Integer
-- tal que (mcd a b) es el máximo común divisor de a y b calculado
-- mediante el algoritmo de Euclides. Por ejemplo,
--    mcd 30 45  ==  15
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo: 
mcd :: Integer -> Integer -> Integer
mcd a b | b == 0 = a
        | b > 0 = mcd b (a `mod` b)

-- ---------------------------------------------------------------------
-- Ejercicio 4. (Problema 5 del proyecto Euler) El problema se encuentra
-- en http://goo.gl/L5bb y consiste en calcular el menor número
-- divisible por los números del 1 al 20. Lo resolveremos mediante los
-- distintos apartados de este ejercicio. 
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir por recursión la función
--    menorDivisible :: Integer -> Integer -> Integer
-- tal que (menorDivisible a b) es el menor número divisible por los
-- números del a al b. Por ejemplo,
--    menorDivisible 2 5  ==  60
-- Indicación: Usar la función lcm tal que (lcm x y) es el mínimo común
-- múltiplo de x e y.
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
menorDivisible :: Integer -> Integer -> Integer
menorDivisible a b | a == b = a
                   | otherwise = lcm a (menorDivisible (a+1) b)

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Definir la constante
--    euler5 :: Integer
-- tal que euler5 es el menor número divisible por los números del 1 al
-- 20 y calcular su valor.
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
euler5 :: Integer
euler5 = menorDivisible 1 20

-- El cálculo es
-- λ> euler5
-- 232792560

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir por recursión la función
--    and' :: [Bool] -> Bool
-- tal que (and' xs) se verifica si todos los elementos de xs son
-- verdadero. Por ejemplo,
--    and' [1+2 < 4, 2:[3] == [2,3]]  ==  True
--    and' [1+2 < 3, 2:[3] == [2,3]]  ==  False
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
and' :: [Bool] -> Bool
and' [] = True
and' (x:xs) = x && and' xs

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir por recursión la función
--    elem' :: Eq a => a -> [a] -> Bool
-- tal que (elem' x xs) se verifica si x pertenece a la lista xs. Por
-- ejemplo, 
--    elem' 3 [2,3,5]  ==  True
--    elem' 4 [2,3,5]  ==  False
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar
elem' :: Eq a => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys) | x == y = True
               | otherwise = elem' x ys

-- Álvaro Galisteo:

elem' :: Eq a => a -> [a] -> Bool
elem' _ [] = False
elem' n (x:xs) = if n == x then True else elem' n xs

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir por recursión la función
--    last' :: [a] -> a
-- tal que (last xs) es el último elemento de xs. Por ejemplo,
--    last' [2,3,5]  =>  5
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
last' :: [a] -> a
last' [x] = x
last' (_:xs) = last' xs

-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir por recursión la función
--    concat' :: [[a]] -> [a]
-- tal que (concat' xss) es la lista obtenida concatenando las listas de
-- xss. Por ejemplo,
--    concat' [[1..3],[5..7],[8..10]]  ==  [1,2,3,5,6,7,8,9,10]
-- ---------------------------------------------------------------------
 
-- Manuel Hidalgo Aguilar
concat' :: [[a]] -> [a]
concat' [] = []
concat' (xs:xss) = xs ++ concat' xss

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir por recursión la función
--    selecciona :: [a] -> Int -> a
-- tal que (selecciona xs n) es el n-ésimo elemento de xs. Por ejemplo,
--    selecciona [2,3,5,7] 2  ==  5 
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
selecciona :: [a] -> Int -> a
selecciona (x:xs) 0 = x
selecciona (x:xs) n = selecciona xs (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir por recursión la función
--    take' :: Int -> [a] -> [a]
-- tal que (take' n xs) es la lista de los n primeros elementos de
-- xs. Por ejemplo, 
--    take' 3 [4..12]  =>  [4,5,6]
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
take' :: Int -> [a] -> [a]
take' 0 xs = []
take' n (x:xs) = [x] ++ take' (n-1) xs

-- ---------------------------------------------------------------------
-- Ejercicio 11. Definir la función
--    refinada :: [Float] -> [Float]
-- tal que (refinada xs) es la lista obtenida intercalando entre cada
-- dos elementos consecutivos de xs su media aritmética. Por ejemplo,
--    refinada [2,7,1,8]  ==  [2.0,4.5,7.0,4.0,1.0,4.5,8.0]
--    refinada [2]        ==  [2.0]
--    refinada []         ==  []
-- ---------------------------------------------------------------------

-- Manuel Hidalgo Aguilar, Álvaro Galisteo:
refinada :: [Float] -> [Float]
refinada (x:y:ys) = [x] ++ [(x+y)/2] ++ refinada (y:ys)
refinada xs = xs