Edición de «Relación 1» - Lógica Matemática y fundamentos (2015-16)

<source lang = "haskell">
-- LMF 2015-16: Rel_1.hs 
-- Introducción a la programación con Haskell.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

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

-- En esta relación de ejercicios hacemos una introducción a Haskell, en
-- la que se recuerdan:
-- * las definiciones elementales de funciones,
-- * las definiciones de funciones por comprensión,
-- * las definiciones de funciones por recursión y
-- * los tipos de datos.

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                  
-- ---------------------------------------------------------------------
 
import Test.QuickCheck
import Data.Char
import Control.Monad

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función media3 tal que (media3 x y z) es
-- la media aritmética de los números x, y y z. Por ejemplo, 
--    media3 1 3 8     ==  4.0
--    media3 (-1) 0 7  ==  2.0
--    media3 (-3) 0 3  ==  0.0
-- ---------------------------------------------------------------------

media3 = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función ultimaCifra tal que (ultimaCifra x)
-- es la última cifra del nímero x. Por ejemplo,
--    ultimaCifra 325  ==  5
-- ---------------------------------------------------------------------

ultimaCifra = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función rota tal que (rota n xs) es la lista
-- obtenida poniendo los n primeros elementos de xs al final de la
-- lista. Por ejemplo, 
--    rota 1 [3,2,5,7]  ==  [2,5,7,3]
--    rota 2 [3,2,5,7]  ==  [5,7,3,2]
--    rota 3 [3,2,5,7]  ==  [7,3,2,5]
-- ---------------------------------------------------------------------

rota = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. La disyunción excluyente xor de dos fórmulas se
-- verifica si una es verdadera y la otra es falsa.
-- 
-- Definir la función xor_1 que calcule la disyunción excluyente a
-- partir de la tabla de verdad. Usar 4 ecuaciones, una por cada línea
-- de la tabla. 
-- ---------------------------------------------------------------------

xor_1 :: Bool -> Bool -> Bool
xor_1 = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Definir la función xor_2 que calcule la disyunción
-- excluyente a partir de la tabla de verdad y patrones. Usar 2
-- ecuaciones, una por cada valor del primer argumento.
-- ---------------------------------------------------------------------

xor_2 :: Bool -> Bool -> Bool
xor_2 = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 4.3. Definir la función xor_3 que calcule la disyunción
-- excluyente a partir de la disyunción (||), conjunción (&&) y negación
-- (not). Usar 1 ecuación.
-- ---------------------------------------------------------------------

xor_3 :: Bool -> Bool -> Bool
xor_3 = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 4.4. Definir la función xor_4 que calcule la disyunción
-- excluyente a partir de desigualdad (/=). Usar 1 ecuación.
-- ---------------------------------------------------------------------

xor_4 :: Bool -> Bool -> Bool
xor_4 = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir, por comprensión, la función
--    sumaDeCuadrados :: Integer -> Integer
-- tal que (sumaDeCuadrados n) es la suma de los cuadrados de los
-- primeros n números; es decir, 1^2 + 2^2 + ... + 100^2. Por ejemplo,
--    sumaDeCuadrados 3    ==  14
--    sumaDeCuadrados 100  ==  338350
-- ---------------------------------------------------------------------

sumaDeCuadrados = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 6. Una terna (x,y,z) de enteros positivos es pitagórica si 
-- x^2 + y^2 = z^2. Usando una lista por comprensión, definir la función
--    pitagoricas :: Int -> [(Int, Int, Int)]
-- tal que (pitagoricas n) es la lista de todas las ternas pitagóricas
-- cuyas componentes están entre 1 y n. Por ejemplo, 
--    *Main> pitagoricas 10 
--    [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
-- ---------------------------------------------------------------------
 
pitagoricas :: Int -> [(Int, Int, Int)]
pitagoricas = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 7. Un entero positivo es perfecto si es igual a la suma de
-- sus factores, excluyendo el propio número. Usando una lista por
-- comprensión y la función factores (del tema), definir la función 
--    perfectos :: Int -> [Int]
-- tal que (perfectos n) es la lista de todos los números perfectos
-- menores que n. Por ejemplo: 
--    *Main> perfectos 500
--    [6,28,496]
-- ---------------------------------------------------------------------
 
perfectos :: Int -> [Int]
perfectos = undefined
 
-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir, por comprensión, la función
--    cuadradosC :: [Integer] -> [Integer]
-- tal que (cuadradosC xs) es la lista de los cuadrados de xs. Por
-- ejemplo, 
--    cuadradosC [1,2,3]  ==  [1,4,9]
-- ---------------------------------------------------------------------

cuadradosC :: [Integer] -> [Integer]
cuadradosC = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir, por recursión, la función
--    cuadradosR :: [Integer] -> [Integer]
-- tal que (cuadradosR xs) es la lista de los cuadrados de xs. Por
-- ejemplo, 
--    cuadradosR [1,2,3]  ==  [1,4,9]
-- ---------------------------------------------------------------------

cuadradosR :: [Integer] -> [Integer]
cuadradosR = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 9.1. Definir, por comprensión, la función
--    imparesC :: [Integer] -> [Integer]
-- tal que (imparesC xs) es la lista de los números impares de xs. Por
-- ejemplo, 
--    imparesC [1,2,3]  ==  [1,3]
-- ---------------------------------------------------------------------

imparesC :: [Integer] -> [Integer]
imparesC = undefined 

-- ---------------------------------------------------------------------
-- Ejercicio 9.2. Definir, por recursión, la función
--    imparesR :: [Integer] -> [Integer]
-- tal que (imparesR xs) es la lista de los números impares de xs. Por
-- ejemplo, 
--    imparesR [1,2,3]  ==  [1,3]
-- ---------------------------------------------------------------------

imparesR :: [Integer] -> [Integer]
imparesR = undefined 

-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir, por comprensión, la función
--    sumaConsecutivos :: [Int] -> [Int]
-- tal que (sumaConsecutivos xs) es la suma de los pares de elementos
-- consecutivos de la lista xs. Por ejemplo,
--    sumaConsecutivos [3,1,5,2]  ==  [4,6,7]
--    sumaConsecutivos [3]        ==  []
-- ---------------------------------------------------------------------

sumaConsecutivos :: [Int] -> [Int]
sumaConsecutivos = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 11.  La distancia de Hamming entre dos listas es el número
-- de posiciones en que los correspondientes elementos son
-- distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba" 
-- es 2 (porque hay 2 posiciones en las que los elementos
-- correspondientes son distintos: la 1ª y la 3ª). 
--    
-- Definir la función distancia tal que (distancia xs ys) es la 
-- distancia de Hamming entre xs e ys. Por ejemplo,
--    distancia "romano" "comino"  ==  2
--    distancia "romano" "camino"  ==  3
--    distancia "roma"   "comino"  ==  2
--    distancia "roma"   "camino"  ==  3
--    distancia "romano" "ron"     ==  1
--    distancia "romano" "cama"    ==  2
--    distancia "romano" "rama"    ==  1
-- ---------------------------------------------------------------------

distancia :: Eq a => [a] -> [a] -> Int
distancia = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 12. Definir la función
--    factoriales :: [Integer]
-- tal que factoriales es la lista de los factoriales. Por ejemplo,
--    take 10 factoriales  ==  [1,1,2,6,24,120,720,5040,40320,362880]
-- ---------------------------------------------------------------------

-- Por comprensión:

factoriales1 :: [Integer]
factoriales1 = undefined

-- Usando zipWith:

factoriales2 :: [Integer]
factoriales2 = undefined

-- Por recursión:

factoriales3 :: [Integer]
factoriales3 = undefined

-- Usando scanl1:

factoriales4 :: [Integer]
factoriales4 = undefined

-- Usando iterate:

factoriales5 :: [Integer]
factoriales5 = undefined

-- Comparación de los tiempos de evaluación:

-- ---------------------------------------------------------------------
-- Ejercicio 13.0. En los siguientes ejercicios se demostrarán
-- propiedades de los árboles binarios definidos como sigue
--    data Arbol a = Hoja 
--                 | Nodo a (Arbol a) (Arbol a)
--                 deriving (Show, Eq)
-- Como ejemplos se usarán los árboles
-- ---------------------------------------------------------------------
 
data Arbol a = Hoja 
             | Nodo a (Arbol a) (Arbol a)
             deriving (Show, Eq)
 
arbol_1 = Nodo 9
               (Nodo 3 
                     (Nodo 2 Hoja Hoja) 
                     (Nodo 4 Hoja Hoja)) 
               (Nodo 7 Hoja Hoja)
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.1. Definir la función
--    espejo :: Arbol a -> Arbol a
-- tal que (espejo x) es la imagen especular del árbol x. Por ejemplo,
--    *Main> espejo arbol_1
--    Nodo 9 
--         (Nodo 7 Hoja Hoja) 
--         (Nodo 3 
--               (Nodo 4 Hoja Hoja) 
--               (Nodo 2 Hoja Hoja))
-- ---------------------------------------------------------------------
 
espejo :: Arbol a -> Arbol a
espejo = undefined
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.2. Comprobar con QuickCheck que para todo árbol x,
--    espejo (espejo x) = x
-- ---------------------------------------------------------------------
 
prop_espejo :: Arbol Int -> Bool
prop_espejo = undefined
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.3. Demostrar por inducción que para todo árbol x,
--    espejo (espejo x) = x
-- ---------------------------------------------------------------------
{-
 Demostración por inducción en x
 
-}
 
 -- ---------------------------------------------------------------------
-- Ejercicio 13.4. Definir la función
--    preorden :: Arbol a -> [a]
-- tal que (preorden x) es la lista correspondiente al recorrido
-- preorden del árbol x; es decir, primero visita la raíz del árbol, a
-- continuación recorre el subárbol izquierdo y, finalmente, recorre el
-- subárbol derecho. Por ejemplo,
--    *Main> arbol_1
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    *Main> preorden arbol_1
--    [9,3,2,4,7]
-- ---------------------------------------------------------------------
 
preorden :: Arbol a -> [a]
preorden = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 13.5. Definir la función
--    postorden :: Arbol a -> [a]
-- tal que (postorden x) es la lista correspondiente al recorrido
-- postorden del árbol x; es decir, primero recorre el subárbol
-- izquierdo, a continuación el subárbol derecho y, finalmente, la raíz
-- del árbol. Por ejemplo,
--    *Main> arbol_1
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    *Main> postorden arbol_1
--    [2,4,3,7,9]
-- ---------------------------------------------------------------------
 
postorden :: Arbol a -> [a]
postorden = undefined
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.6. Comprobar con QuickCheck que para todo árbol x,
--    postorden (espejo x) = reverse (preorden x)
-- ---------------------------------------------------------------------
 
-- La propiedad es
prop_recorrido :: Arbol Int -> Bool
prop_recorrido = undefined
 
-- La comprobación es
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.7. Demstrar por inducción que para todo árbol x,
--    postorden (espejo x) = reverse (preorden x)
-- ---------------------------------------------------------------------
 
{-
 Demostración por inducción en x.

-}
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.8. Comprobar con QuickCheck que para todo árbol binario
-- x, se tiene que
--    reverse (preorden (espejo x)) = postorden x
-- ---------------------------------------------------------------------
 
-- La propiedad es
prop_reverse_preorden_espejo :: Arbol Int -> Bool
prop_reverse_preorden_espejo x =
   reverse (preorden (espejo x)) == postorden x
 
-- La comprobación es
--    *Main> quickCheck prop_reverse_preorden_espejo
--    OK, passed 100 tests.
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.9. Demostrar que para todo árbol binario x, se tiene que
--    reverse (preorden (espejo x)) = preorden x
-- ---------------------------------------------------------------------
 
{-
 Demostración:
    reverse (preorden (espejo x))
    = postorden (espejo (espejo x))    [por ejercicio 13.7]
    = postorden x                      [por ejercicio 13.3]
-}
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.10. Definir la función
--    nNodos :: Arbol a -> Int
-- tal que (nNodos x) es el número de nodos del árbol x. Por ejemplo,
--    *Main> arbol_1
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    *Main> nNodos arbol_1
--    5
-- ---------------------------------------------------------------------
 
nNodos :: Arbol a -> Int
nNodos = undefined
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.11. Comprobar con QuickCheck que el número de nodos de la
-- imagen especular de un árbol es el mismo que el número de nodos del
-- árbol. 
-- ---------------------------------------------------------------------
 
-- La propiedad es
prop_nNodos_espejo :: Arbol Int -> Bool
prop_nNodos_espejo = undefined
 
-- La comprobación es
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.12. Demostrar por inducción que el número de nodos de la
-- imagen especular de un árbol es el mismo que el número de nodos del
-- árbol. 
-- ---------------------------------------------------------------------
 
{-
 Demostración: 

-}
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.13. Comprobar con QuickCheck que la longitud de la lista
-- obtenida recorriendo un árbol en sentido preorden es igual al número
-- de nodos del árbol.
-- ---------------------------------------------------------------------
 
-- La propiedad es
prop_length_preorden :: Arbol Int -> Bool
prop_length_preorden = undefined
 
-- La comprobación es
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.14. Demostrar por inducción que la longitud de la lista
-- obtenida recorriendo un árbol en sentido preorden es igual al número
-- de nodos del árbol.
-- ---------------------------------------------------------------------
 
{-
 Demostración: 

-}
 
-- ---------------------------------------------------------------------
-- Ejercicio 13.15. Definir la función
--    profundidad :: Arbol a -> Int
-- tal que (profundidad x) es la profundidad del árbol x. Por ejemplo,
--    *Main> arbol_1
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    *Main> profundidad arbol_1
--    3
-- ---------------------------------------------------------------------
 
profundidad :: Arbol a -> Int
profundidad = undefined 

-- ---------------------------------------------------------------------
-- Ejercicio 13.16. Comprobar con QuickCheck que para todo árbol binario
-- x, se tiene que
--    nNodos x <= 2^(profundidad x) - 1
-- ---------------------------------------------------------------------
 
-- La propiedad es
prop_nNodosProfundidad :: Arbol Int -> Bool
prop_nNodosProfundidad = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Nota. Para comprobar propiedades de árboles con QuickCheck se
-- utilizará el siguiente generador.
-- ---------------------------------------------------------------------


instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbol
    where
      arbol 0       = return Hoja 
      arbol n | n>0 = oneof [return Hoja,
                             liftM3 Nodo arbitrary subarbol subarbol]
                      where subarbol = arbol (div n 2)

</haskell>