Lógica Matemática y fundamentos (2015-16) - Contribuciones del usuario [es]

Relación 1

2016-02-28T12:46:44Z

Rosriomar:

<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 :: Float -> Float -> Float -> Float
media3 x y z = (x+y+z)/3

-- ---------------------------------------------------------------------
-- 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 :: Integer -> Integer
ultimaCifra x = abs(rem x 10)

-- ---------------------------------------------------------------------
-- 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 :: Int -> [a] -> [a]
rota n xs | n < length xs = (drop n xs)++(take n xs)
|otherwise = rota ( mod n (length xs)) xs

-- ---------------------------------------------------------------------
-- 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 True True = False
xor_1 True False = True
xor_1 False True = True
xor_1 False False = False

-- ---------------------------------------------------------------------
-- 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 True q = not q
xor_2 False q = q
-- ---------------------------------------------------------------------
-- 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 p q = (p && (not q)) || ((not p) && q)

-- ---------------------------------------------------------------------
-- 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 p q = p /= q

-- ---------------------------------------------------------------------
-- 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 :: Integer -> Integer
sumaDeCuadrados n = sum (map (^2) [1..n])

--otra forma:
sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = sum [x^2 | x <- [1..n]]

-- ---------------------------------------------------------------------
-- 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 n = [(a,b,c)|a<-[1..n],b<-[1..n], c<-[1..n], a^2 + b^2==c^2]

-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------
factores :: Int -> [Int]
factores n = [x|x<-[1..(div n 2)], mod n x ==0]
perfectos :: Int -> [Int]
perfectos n = [x|x<-[1..n], sum (factores x)== x]

-- Otra forma
factores :: Int -> [Int]
factores n = [x|x<-[1..n],mod n x == 0]

perfectos :: Int -> [Int]
perfectos n = [i|i<-[1..(n-1)],i==(sum((factores i))-i)]

-- ---------------------------------------------------------------------
-- 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 xs= [y^2| y<-xs]

-- ---------------------------------------------------------------------
-- 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 [] = []
cuadradoR (x:xs) = [x^2] ++ cuadradosR xs

-- otra forma
cuadradosR :: [Integer] -> [Integer]
cuadradosR []=[]
cuadradosR (x:xs) = (x^2):cuadradosR xs

-- ---------------------------------------------------------------------
-- 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 xs = [x|x<-xs, odd x]
-- ---------------------------------------------------------------------
-- 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 []= []
imparesR (x:xs) | odd x= x: (imparesR xs)
| otherwise = imparesR xs

-- ---------------------------------------------------------------------
-- 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 xs = zipWith (+) xs (tail xs)

-- ---------------------------------------------------------------------
-- 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 [] _ = 0
distancia _ [] = 0
distancia (x:xs) (y:ys) | x==y= distancia xs ys
|otherwise = 1 + distancia xs ys

-- ---------------------------------------------------------------------
-- 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 = 1:[factorial x|x<-[1..]]
factorial x = product[1..x]

--otra forma sin necesidad de añadir el 1 a la lista

factoriales1 :: [Integer]
factoriales1 = [product [1..n]|n<-[0..]]

-- Usando zipWith:

factoriales2 :: [Integer]
factoriales2 = 1: zipWith (*) [1..] factoriales2

-- Por recursión:

factoriales3 :: [Integer]
factoriales3 = 1: (aux 1 [1..])
where aux n (x:xs) = (n*x):(aux (n*x) xs)

--otra forma
factoriales3 :: [Integer]
factoriales3 = aux (1,1)
where aux (x,y) = x: aux (x*y,y+1)

-- Usando scanl1:

factoriales4 :: [Integer]
factoriales4 = 1:scanl1 (*) [1..]

-- Usando iterate:

factoriales5 :: [Integer]
factoriales5 = map snd aux
where aux = iterate aux2 (1,1) where aux2 (x,y) = (x+1,x*y)

--otra forma
factoriales5 :: [Integer]
factoriales5 = map (fst) (iterate (\(x,y)->(x*y,y+1)) (1,1))

-- Comparación de los tiempos de evaluación:
-- *Main> :set +s
-- take 100 factoriales1 -> (0.20 secs, 0 bytes)
-- take 100 factoriales2 -> (0.05 secs, 0 bytes)
-- take 100 factoriales3 -> (0.02 secs, 0 bytes)
-- take 100 factoriales4 -> (0.00 secs, 20,605,760 bytes)
-- take 100 factoriales5 -> (0.02 secs, 0 bytes)

-- ---------------------------------------------------------------------
-- 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 Hoja = Hoja
espejo (Nodo a i d) = Nodo a (espejo d) (espejo i)

-- ---------------------------------------------------------------------
-- Ejercicio 13.2. Comprobar con QuickCheck que para todo árbol x,
-- espejo (espejo x) = x
-- ---------------------------------------------------------------------

prop_espejo :: Arbol Int -> Bool
prop_espejo x = espejo (espejo x) == x

-- ---------------------------------------------------------------------
-- Ejercicio 13.3. Demostrar por inducción que para todo árbol x,
-- espejo (espejo x) = x
-- ---------------------------------------------------------------------
{-
-- Demostración por inducción en x
-- Caso base: El árbol es una Hoja. Por definición de espejo, espejo Hoja = Hoja, luego espejo (espejo Hoja) = Hoja.
-- Caso inductivo: El árbol tiene profundidad n. Se supone cierto que para este árbol se verifica que espejo (espejo x) = x
-- Demostración para un árbol de profundidad (n+1). Este árbol es de la forma (Nodo a i d) donde i, d son árboles de profundidad igual o menor
-- que n.
-- espejo (espejo (Nodo a i d)) = espejo (Nodo a (espejo d) (espejo i)) = Nodo a (espejo(espejo i)) (espejo(espejo d)) por definición de la
-- función espejo. Por hipótesis de inducción espejo(espejo i) = i y espejo(espejo d) = d, y queda demostrado.
-}

-- ---------------------------------------------------------------------
-- 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 Hoja = []
preorden (Nodo a i d)= a:(preorden i)++(preorden d)

-- ---------------------------------------------------------------------
-- 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 Hoja = []
postorden (Nodo a i d) = (postorden i)++(postorden d)++[a]

-- ---------------------------------------------------------------------
-- 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 x = postorden (espejo x) == reverse (preorden x)

-- 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 Hoja = 0
nNodos (Nodo n i d) = 1 + nNodos i + nNodos d

-- ---------------------------------------------------------------------
-- 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 x =
nNodos (espejo x) == nNodos x

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

-- ---------------------------------------------------------------------
-- 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 x =
length (preorden x) == length (postorden x)

--
prop_length_preorden :: Arbol Int -> Bool
prop_length_preorden x = length(preorden x) == nNodos x

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

-- ---------------------------------------------------------------------
-- 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 Hoja = 0
profundidad (Nodo n i d)
| length (preorden i) > length (preorden d) = 1 + profundidad i
| otherwise = 1 + profundidad d

-- ---------------------------------------------------------------------
-- 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 x =
nNodos x <= 2^(profundidad x) - 1

-- La comprobación es
-- quickCheck prop_nNodosProfundidad
-- +++ OK, passed 100 tests.

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

</source>

Relación 1

2016-02-26T12:23:03Z

Rosriomar:

<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 :: Float -> Float -> Float -> Float
media3 x y z = (x+y+z)/3

-- ---------------------------------------------------------------------
-- 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 :: Integer -> Integer
ultimaCifra x = abs(rem x 10)

-- ---------------------------------------------------------------------
-- 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 :: Int -> [a] -> [a]
rota n xs | n < length xs = (drop n xs)++(take n xs)
|otherwise = rota ( mod n (length xs)) xs

-- ---------------------------------------------------------------------
-- 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 True True = False
xor_1 True False = True
xor_1 False True = True
xor_1 False False = False

-- ---------------------------------------------------------------------
-- 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 True q = not q
xor_2 False q = q
-- ---------------------------------------------------------------------
-- 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 p q = (p && (not q)) || ((not p) && q)

-- ---------------------------------------------------------------------
-- 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 p q = p /= q

-- ---------------------------------------------------------------------
-- 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 :: Integer -> Integer
sumaDeCuadrados n = sum (map (^2) [1..n])

--otra forma:
sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = sum [x^2 | x <- [1..n]]

-- ---------------------------------------------------------------------
-- 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 n = [(a,b,c)|a<-[1..n],b<-[1..n], c<-[1..n], a^2 + b^2==c^2]

-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------
factores :: Int -> [Int]
factores n = [x|x<-[1..(div n 2)], mod n x ==0]
perfectos :: Int -> [Int]
perfectos n = [x|x<-[1..n], sum (factores x)== x]

-- Otra forma
factores :: Int -> [Int]
factores n = [x|x<-[1..n],mod n x == 0]

perfectos :: Int -> [Int]
perfectos n = [i|i<-[1..(n-1)],i==(sum((factores i))-i)]

-- ---------------------------------------------------------------------
-- 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 xs= [y^2| y<-xs]

-- ---------------------------------------------------------------------
-- 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 [] = []
cuadradoR (x:xs) = [x^2] ++ cuadradosR xs

-- otra forma
cuadradosR :: [Integer] -> [Integer]
cuadradosR []=[]
cuadradosR (x:xs) = (x^2):cuadradosR xs

-- ---------------------------------------------------------------------
-- 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 xs = [x|x<-xs, odd x]
-- ---------------------------------------------------------------------
-- 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 []= []
imparesR (x:xs) | odd x= x: (imparesR xs)
| otherwise = imparesR xs

-- ---------------------------------------------------------------------
-- 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 xs = zipWith (+) xs (tail xs)

-- ---------------------------------------------------------------------
-- 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 [] _ = 0
distancia _ [] = 0
distancia (x:xs) (y:ys) | x==y= distancia xs ys
|otherwise = 1 + distancia xs ys

-- ---------------------------------------------------------------------
-- 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 = 1:[factorial x|x<-[1..]]
factorial x = product[1..x]

--otra forma sin necesidad de añadir el 1 a la lista

factoriales1 :: [Integer]
factoriales1 = [product [1..n]|n<-[0..]]

-- Usando zipWith:

factoriales2 :: [Integer]
factoriales2 = 1: zipWith (*) [1..] factoriales2

-- Por recursión:

factoriales3 :: [Integer]
factoriales3 = 1: (aux 1 [1..])
where aux n (x:xs) = (n*x):(aux (n*x) xs)

--otra forma
factoriales3 :: [Integer]
factoriales3 = aux (1,1)
where aux (x,y) = x: aux (x*y,y+1)

-- Usando scanl1:

factoriales4 :: [Integer]
factoriales4 = 1:scanl1 (*) [1..]

-- Usando iterate:

factoriales5 :: [Integer]
factoriales5 = map snd aux
where aux = iterate aux2 (1,1) where aux2 (x,y) = (x+1,x*y)

--otra forma
factoriales5 :: [Integer]
factoriales5 = map (fst) (iterate (\(x,y)->(x*y,y+1)) (1,1))

-- Comparación de los tiempos de evaluación:
-- *Main> :set +s
-- take 100 factoriales1 -> (0.20 secs, 0 bytes)
-- take 100 factoriales2 -> (0.05 secs, 0 bytes)
-- take 100 factoriales3 -> (0.02 secs, 0 bytes)
-- take 100 factoriales4 -> (0.00 secs, 20,605,760 bytes)
-- take 100 factoriales5 -> (0.02 secs, 0 bytes)

-- ---------------------------------------------------------------------
-- 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 Hoja = Hoja
espejo (Nodo a i d) = Nodo a (espejo d) (espejo i)

-- ---------------------------------------------------------------------
-- Ejercicio 13.2. Comprobar con QuickCheck que para todo árbol x,
-- espejo (espejo x) = x
-- ---------------------------------------------------------------------

prop_espejo :: Arbol Int -> Bool
prop_espejo x = espejo (espejo x) == x

-- ---------------------------------------------------------------------
-- Ejercicio 13.3. Demostrar por inducción que para todo árbol x,
-- espejo (espejo x) = x
-- ---------------------------------------------------------------------
{-
-- Demostración por inducción en x
-- Caso base: El árbol es una Hoja. Por definición de espejo, espejo Hoja = Hoja, luego espejo (espejo Hoja) = Hoja.
-- Caso inductivo: El árbol tiene profundidad n. Se supone cierto que para este árbol se verifica que espejo (espejo x) = x
-- Demostración para un árbol de profundidad (n+1). Este árbol es de la forma (Nodo a i d) donde i, d son árboles de profundidad igual o menor
-- que n.
-- espejo (espejo (Nodo a i d)) = espejo (Nodo a (espejo d) (espejo i)) = Nodo a (espejo(espejo i)) (espejo(espejo d)) por definición de la
-- función espejo. Por hipótesis de inducción espejo(espejo i) = i y espejo(espejo d) = d, y queda demostrado.
-}

-- ---------------------------------------------------------------------
-- 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 Hoja = []
preorden (Nodo a i d)= a:(preorden i)++(preorden d)

-- ---------------------------------------------------------------------
-- 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 Hoja = []
postorden (Nodo a i d) = (postorden i)++(postorden d)++[a]

-- ---------------------------------------------------------------------
-- 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 x = postorden (espejo x) == reverse (preorden x)

-- 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 Hoja = 0
nNodos (Nodo n i d) = 1 + nNodos i + nNodos d

-- ---------------------------------------------------------------------
-- 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 x =
nNodos (espejo x) == nNodos x

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

-- ---------------------------------------------------------------------
-- 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 x =
length (preorden x) == length (postorden x)

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

-- ---------------------------------------------------------------------
-- 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 Hoja = 0
profundidad (Nodo n i d)
| length (preorden i) > length (preorden d) = 1 + profundidad i
| otherwise = 1 + profundidad d

-- ---------------------------------------------------------------------
-- 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 x =
nNodos x <= 2^(profundidad x) - 1

-- La comprobación es
-- quickCheck prop_nNodosProfundidad
-- +++ OK, passed 100 tests.

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

</source>

Relación 1

2016-02-26T12:16:13Z

Rosriomar:

<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 :: Float -> Float -> Float -> Float
media3 x y z = (x+y+z)/3

-- ---------------------------------------------------------------------
-- 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 :: Integer -> Integer
ultimaCifra x = abs(rem x 10)

-- ---------------------------------------------------------------------
-- 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 :: Int -> [a] -> [a]
rota n xs | n < length xs = (drop n xs)++(take n xs)
|otherwise = rota ( mod n (length xs)) xs

-- ---------------------------------------------------------------------
-- 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 True True = False
xor_1 True False = True
xor_1 False True = True
xor_1 False False = False

-- ---------------------------------------------------------------------
-- 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 True q = not q
xor_2 False q = q
-- ---------------------------------------------------------------------
-- 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 p q = (p && (not q)) || ((not p) && q)

-- ---------------------------------------------------------------------
-- 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 p q = p /= q

-- ---------------------------------------------------------------------
-- 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 :: Integer -> Integer
sumaDeCuadrados n = sum (map (^2) [1..n])

--otra forma:
sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = sum [x^2 | x <- [1..n]]

-- ---------------------------------------------------------------------
-- 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 n = [(a,b,c)|a<-[1..n],b<-[1..n], c<-[1..n], a^2 + b^2==c^2]

-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------
factores :: Int -> [Int]
factores n = [x|x<-[1..(div n 2)], mod n x ==0]
perfectos :: Int -> [Int]
perfectos n = [x|x<-[1..n], sum (factores x)== x]

-- Otra forma
factores :: Int -> [Int]
factores n = [x|x<-[1..n],mod n x == 0]

perfectos :: Int -> [Int]
perfectos n = [i|i<-[1..(n-1)],i==(sum((factores i))-i)]

-- ---------------------------------------------------------------------
-- 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 xs= [y^2| y<-xs]

-- ---------------------------------------------------------------------
-- 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 [] = []
cuadradoR (x:xs) = [x^2] ++ cuadradosR xs

-- ---------------------------------------------------------------------
-- 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 xs = [x|x<-xs, odd x]
-- ---------------------------------------------------------------------
-- 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 []= []
imparesR (x:xs) | odd x= x: (imparesR xs)
| otherwise = imparesR xs

-- ---------------------------------------------------------------------
-- 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 xs = zipWith (+) xs (tail xs)

-- ---------------------------------------------------------------------
-- 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 [] _ = 0
distancia _ [] = 0
distancia (x:xs) (y:ys) | x==y= distancia xs ys
|otherwise = 1 + distancia xs ys

-- ---------------------------------------------------------------------
-- 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 = 1:[factorial x|x<-[1..]]
factorial x = product[1..x]

--otra forma sin necesidad de añadir el 1 a la lista

factoriales1 :: [Integer]
factoriales1 = [product [1..n]|n<-[0..]]

-- Usando zipWith:

factoriales2 :: [Integer]
factoriales2 = 1: zipWith (*) [1..] factoriales2

-- Por recursión:

factoriales3 :: [Integer]
factoriales3 = 1: (aux 1 [1..])
where aux n (x:xs) = (n*x):(aux (n*x) xs)

--otra forma
factoriales3 :: [Integer]
factoriales3 = aux (1,1)
where aux (x,y) = x: aux (x*y,y+1)

-- Usando scanl1:

factoriales4 :: [Integer]
factoriales4 = 1:scanl1 (*) [1..]

-- Usando iterate:

factoriales5 :: [Integer]
factoriales5 = map snd aux
where aux = iterate aux2 (1,1) where aux2 (x,y) = (x+1,x*y)

--otra forma
factoriales5 :: [Integer]
factoriales5 = map (fst) (iterate (\(x,y)->(x*y,y+1)) (1,1))

-- Comparación de los tiempos de evaluación:
-- *Main> :set +s
-- take 100 factoriales1 -> (0.20 secs, 0 bytes)
-- take 100 factoriales2 -> (0.05 secs, 0 bytes)
-- take 100 factoriales3 -> (0.02 secs, 0 bytes)
-- take 100 factoriales4 -> (0.00 secs, 20,605,760 bytes)
-- take 100 factoriales5 -> (0.02 secs, 0 bytes)

-- ---------------------------------------------------------------------
-- 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 Hoja = Hoja
espejo (Nodo a i d) = Nodo a (espejo d) (espejo i)

-- ---------------------------------------------------------------------
-- Ejercicio 13.2. Comprobar con QuickCheck que para todo árbol x,
-- espejo (espejo x) = x
-- ---------------------------------------------------------------------

prop_espejo :: Arbol Int -> Bool
prop_espejo x = espejo (espejo x) == x

-- ---------------------------------------------------------------------
-- Ejercicio 13.3. Demostrar por inducción que para todo árbol x,
-- espejo (espejo x) = x
-- ---------------------------------------------------------------------
{-
-- Demostración por inducción en x
-- Caso base: El árbol es una Hoja. Por definición de espejo, espejo Hoja = Hoja, luego espejo (espejo Hoja) = Hoja.
-- Caso inductivo: El árbol tiene profundidad n. Se supone cierto que para este árbol se verifica que espejo (espejo x) = x
-- Demostración para un árbol de profundidad (n+1). Este árbol es de la forma (Nodo a i d) donde i, d son árboles de profundidad igual o menor
-- que n.
-- espejo (espejo (Nodo a i d)) = espejo (Nodo a (espejo d) (espejo i)) = Nodo a (espejo(espejo i)) (espejo(espejo d)) por definición de la
-- función espejo. Por hipótesis de inducción espejo(espejo i) = i y espejo(espejo d) = d, y queda demostrado.
-}

-- ---------------------------------------------------------------------
-- 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 Hoja = []
preorden (Nodo a i d)= a:(preorden i)++(preorden d)

-- ---------------------------------------------------------------------
-- 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 Hoja = []
postorden (Nodo a i d) = (postorden i)++(postorden d)++[a]

-- ---------------------------------------------------------------------
-- 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 x = postorden (espejo x) == reverse (preorden x)

-- 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 Hoja = 0
nNodos (Nodo n i d) = 1 + nNodos i + nNodos d

-- ---------------------------------------------------------------------
-- 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 x =
nNodos (espejo x) == nNodos x

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

-- ---------------------------------------------------------------------
-- 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 x =
length (preorden x) == length (postorden x)

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

-- ---------------------------------------------------------------------
-- 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 Hoja = 0
profundidad (Nodo n i d)
| length (preorden i) > length (preorden d) = 1 + profundidad i
| otherwise = 1 + profundidad d

-- ---------------------------------------------------------------------
-- 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 x =
nNodos x <= 2^(profundidad x) - 1

-- La comprobación es
-- quickCheck prop_nNodosProfundidad
-- +++ OK, passed 100 tests.

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

</source>