Lógica matemática y fundamentos (2014-15) - Contribuciones del usuario [es]

Relación 2a

2015-06-06T16:31:06Z

Nikdro:

<source lang = "haskell">
-- SintaxisSemanticaProp.hs
-- Lógica proposicional: Sintaxis y semántica
-- José A. Alonso Jiménez <jalonso@us.es>
-- ---------------------------------------------------------------------

module SintaxisSemantica where

-- ---------------------------------------------------------------------
-- Librerías auxiliares --
-- ---------------------------------------------------------------------

import Data.List

-- ---------------------------------------------------------------------
-- Gramática de fórmulas prosicionales --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 1: Definir los siguientes tipos de datos:
-- * SímboloProposicional para representar los símbolos de proposiciones
-- * Prop para representar las fórmulas proposicionales usando los
-- constructores Atom, Neg, Conj, Disj, Impl y Equi para las fórmulas
-- atómicas, negaciones, conjunciones, implicaciones y equivalencias,
-- respectivamente.
-- ---------------------------------------------------------------------

type SímboloProposicional = String

data Prop = Atom SímboloProposicional
| Neg Prop
| Conj Prop Prop
| Disj Prop Prop
| Impl Prop Prop
| Equi Prop Prop
deriving (Eq,Ord)

instance Show Prop where
show (Atom p) = p
show (Neg p) = "no " ++ show p
show (Conj p q) = "(" ++ show p ++ " /\\ " ++ show q ++ ")"
show (Disj p q) = "(" ++ show p ++ " \\/ " ++ show q ++ ")"
show (Impl p q) = "(" ++ show p ++ " --> " ++ show q ++ ")"
show (Equi p q) = "(" ++ show p ++ " <--> " ++ show q ++ ")"

-- ---------------------------------------------------------------------
-- Ejercicio 2: Definir las siguientes fórmulas proposicionales
-- atómicas: p, p1, p2, q, r, s, t y u.
-- ---------------------------------------------------------------------

p, p1, p2, q, r, s, t, u :: Prop
p = Atom "p"
p1 = Atom "p1"
p2 = Atom "p2"
q = Atom "q"
r = Atom "r"
s = Atom "s"
t = Atom "t"
u = Atom "u"

-- ---------------------------------------------------------------------
-- Ejercicio 3: Definir la función
-- no :: Prop -> Prop
-- tal que (no f) es la negación de f.
-- ---------------------------------------------------------------------

no :: Prop -> Prop
no = Neg

-- ---------------------------------------------------------------------
-- Ejercicio 4: Definir los siguientes operadores
-- (/\), (\/), (-->), (<-->) :: Prop -> Prop -> Prop
-- tales que
-- f /\ g es la conjunción de f y g
-- f \/ g es la disyunción de f y g
-- f --> g es la implicación de f a g
-- f <--> g es la equivalencia entre f y g
-- ---------------------------------------------------------------------

infixr 5 \/
infixr 4 /\
infixr 3 -->
infixr 2 <-->
(/\), (\/), (-->), (<-->) :: Prop -> Prop -> Prop
(/\) = Conj
(\/) = Disj
(-->) = Impl
(<-->) = Equi

-- ---------------------------------------------------------------------
-- Símbolos proposicionales de una fórmula --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 5: Definir la función
-- símbolosPropFórm :: Prop -> [Prop]
-- tal que (símbolosPropFórm f) es el conjunto formado por todos los
-- símbolos proposicionales que aparecen en f. Por ejemplo,
-- símbolosPropFórm (p /\ q --> p) ==> [p,q]
-- ---------------------------------------------------------------------

simbolosPropForm :: Prop -> [Prop]
simbolosPropForm (Atom p) = [Atom p]
simbolosPropForm (Neg p) = simbolosPropForm p
simbolosPropForm (Conj p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))
simbolosPropForm (Disj p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))
simbolosPropForm (Impl p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))
simbolosPropForm (Equi p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))

-- Luis Curquejo

-- Comentario: La definición se puede mejorar usando la función union.

-- ---------------------------------------------------------------------
-- Interpretaciones --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 6: Definir el tipo de datos Interpretación para
-- representar las interpretaciones como listas de fórmulas atómicas.
-- ---------------------------------------------------------------------

type Interpretación = [Prop]

-- ---------------------------------------------------------------------
-- Significado de una fórmula en una interpretación --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 7: Definir la función
-- significado :: Prop -> Interpretación -> Bool
-- tal que (significado f i) es el significado de f en i. Por ejemplo,
-- significado ((p \/ q) /\ ((no q) \/ r)) [r] ==> False
-- significado ((p \/ q) /\ ((no q) \/ r)) [p,r] ==> True
-- ---------------------------------------------------------------------

significado :: Prop -> Interpretacion -> Bool
significado (Atom f) xs | elem (Atom f) xs = True
| otherwise = False
significado (Neg f) xs = not (significado f xs)
significado (Conj f q) xs = (significado f xs) && (significado q xs)
significado (Disj f q) xs = (significado f xs) || (significado q xs)
significado (Impl f q) xs | (significado f xs) == True = significado q xs
| otherwise = True
significado (Equi f q) xs = (significado f xs) == (significado q xs)

--Luis Curquejo

-- Comentario: la definición se puede simplificar.

significado :: Prop -> Interpretacion -> Bool
significado (Atom p) i = elem (Atom p) i
significado (Neg p) i = not (significado p i)
significado (Conj p q) i = (significado p i)&&(significado q i)
significado (Disj p q) i = (significado p i)||(significado q i)
significado (Impl p q) i | significado p i = significado q i
| otherwise = True
significado (Equi p q) i = (significado p i)==(significado q i)

--María Dolores Mateo Ceballos

significado (Impl p q) i = (significado p i) <= (significado q i)

--Nikola Drousie (el resto sería igual que María Dolores)

-- ---------------------------------------------------------------------
-- Interpretaciones de una fórmula --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 8: Definir la función
-- subconjuntos :: [a] -> [[a]]
-- tal que (subconjuntos x) es la lista de los subconjuntos de x. Por
-- ejmplo,
-- subconjuntos "abc" ==> ["abc","ab","ac","a","bc","b","c",""]
-- ---------------------------------------------------------------------

subconjuntos :: [a] -> [[a]]
subconjuntos [] = [[]]
subconjuntos [a] = [[],[a]]
subconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub
where sub = subconjuntos xs
-- Me acordaba de primero (seguro) Javier Rodríguez Vivas
-- Jaime Alberto

subconjuntos :: [a] -> [[a]]
subconjuntos [] = [[]]
subconjuntos (x:xs) = [x:ys | ys<-subconjuntos xs] ++ subconjuntos xs

-- ---------------------------------------------------------------------
-- Ejercicio 9: Definir la función
-- interpretacionesFórm :: Prop -> [Interpretación]
-- tal que (interpretacionesFórm f) es la lista de todas las
-- interpretaciones de f. Por ejemplo,
-- interpretacionesFórm (p /\ q --> p) ==> [[p,q],[p],[q],[]]
-- ---------------------------------------------------------------------

interpretacionesForm :: Prop -> [Interpretacion]
interpretacionesForm f = subconjuntos (simbolosPropForm f)

--Luis Curquejo

-- ---------------------------------------------------------------------
-- Modelos de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 10: Definir la función
-- esModeloFórmula :: Interpretación -> Prop -> Bool
-- tal que (esModeloFórmula i f) se verifica si i es un modelo de f. Por
-- ejemplo,
-- esModeloFórmula [r] ((p \/ q) /\ ((no q) \/ r)) ==> False
-- esModeloFórmula [p,r] ((p \/ q) /\ ((no q) \/ r)) ==> True
-- ---------------------------------------------------------------------

esModeloFormula :: Interpretacion -> Prop -> Bool
esModeloFormula i f = significado f i

-- Luis Curquejo
-- Francisco Javier Carmona

-- ---------------------------------------------------------------------
-- Ejercicio 11: Definir la función
-- modelosFórmula :: Prop -> [Interpretación]
-- tal que (modelosFórmula f) es la lista de todas las interpretaciones
-- de f que son modelo de F. Por ejemplo,
-- modelosFórmula ((p \/ q) /\ ((no q) \/ r))
-- ==> [[p,q,r],[p,r],[p],[q,r]]
-- ---------------------------------------------------------------------

modelosFórmula :: Prop -> [Interpretación]
modelosFórmula f = [i | i <- subconjuntos (símbolosPropFórm f), esModeloFórmula i f]

-- Elisa Mazuelos Jiménez

-- Comentario: la definición se puede simplificar usando interpretacionesForm.

modelosFormula :: Prop -> [Interpretacion]
modelosFormula f = [xs|xs<-(interpretacionesForm f), esModeloFormula xs f]

--María Dolores Mateo Ceballos

modelosFormula :: Prop -> [Interpretacion]
modelosFormula f = aux (interpretacionesForm f)
where aux [] = []
aux (x:xs) | esModeloFormula x f = x : aux xs
| otherwise = aux xs

-- Francisco Javier Carmona

-- ---------------------------------------------------------------------
-- Fórmulas válidas, satisfacibles e insatisfacibles --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 12: Definir la función
-- esVálida :: Prop -> Bool
-- tal que (esVálida f) se verifica si f es válida. Por ejemplo,
-- esVálida (p --> p) ==> True
-- esVálida (p --> q) ==> False
-- esVálida ((p --> q) \/ (q --> p)) ==> True
-- ---------------------------------------------------------------------

esValida :: Prop -> Bool
esValida f = subconjuntos (simPro f) == modelosFormula f

-- Javier Rodríguez Vivas

-- Comentario: la definición se puede simplificar usando interpretacionesForm.

esValida :: Prop -> Bool
esValida f = modelosFormula f == interpretacionesForm f

-- María Dolores Mateo Ceballos
-- Francisco Javier Carmona

-- ---------------------------------------------------------------------
-- Ejercicio 13: Definir la función
-- esInsatisfacible :: Prop -> Bool
-- tal que (esInsatisfacible f) se verifica si f es insatisfacible. Por
-- ejemplo,
-- esInsatisfacible (p /\ (no p)) ==> True
-- esInsatisfacible ((p --> q) /\ (q --> r)) ==> False
-- ---------------------------------------------------------------------

esInsatisfacible :: Prop -> Bool
esInsatisfacible f = null (modelosFórmula f)
--Emilio Martinez Rivero

esInsatisfacible :: Prop -> Bool
esInsatisfacible f = modelosFormula f == []

-- Francisco Javier Carmona

-- ---------------------------------------------------------------------
-- Ejercicio 14: Definir la función
-- esSatisfacible :: Prop -> Bool
-- tal que (esSatisfacible f) se verifica si f es satisfacible. Por
-- ejemplo,
-- esSatisfacible (p /\ (no p)) ==> False
-- esSatisfacible ((p --> q) /\ (q --> r)) ==> True
-- ---------------------------------------------------------------------

esSatisfacible :: Prop -> Bool
esSatisfacible = not . EsInsatisfacible
--Emilio Martinez Rivero

esSatisfacible :: Prop -> Bool
esSatisfacible f = modelosFormula f /= []

-- Francisco Javier Carmona

-- ---------------------------------------------------------------------
-- Símbolos proposicionales de un conjunto de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 15: Definir la función
-- uniónGeneral :: Eq a => [[a]] -> [a]
-- tal que (uniónGeneral x) es la unión de los conjuntos de la lista de
-- conjuntos x. Por ejemplo,
-- uniónGeneral [] ==> []
-- uniónGeneral [[1]] ==> [1]
-- uniónGeneral [[1],[1,2],[2,3]] ==> [1,2,3]
-- ---------------------------------------------------------------------

unionGeneral :: Eq a => [[a]] -> [a]
unionGeneral [] = []
unionGeneral (x:xs) = nub(x++ unionGeneral xs)

--Javier Rodríguez Vivas
-- Francisco Javier Carmona

-- Comentario: La definición se puede mejorar usando la función union.

uniónGeneral :: Eq a => [[a]] -> [a]
uniónGeneral = nub . concat

-- Elisa Mazuelos Jiménez

unionGeneral :: Eq a => [[a]] -> [a]
unionGeneral [] = []
unionGeneral (xs:xss) = union xs (unionGeneral xss)

-- Maria del Carmen Mesa Marquez

-- ---------------------------------------------------------------------
-- Ejercicio 16: Definir la función
-- símbolosPropConj :: [Prop] -> [Prop]
-- tal que (símbolosPropConj s) es el conjunto de los símbolos
-- proposiciones de s. Por ejemplo,
-- símbolosPropConj [p /\ q --> r, p --> s] ==> [p,q,r,s]
-- ---------------------------------------------------------------------

símbolosPropConj :: [Prop] -> [Prop]
símbolosPropConj s = uniónGeneral [simb x | x<-s]

--Emilio Martinez Rivero

simbolosPropConj :: [Prop] -> [Prop]
simbolosPropConj s = nub (aux s)
where aux [] = []
aux (x:xs) = simbolosPropForm x ++
simbolosPropConj xs

-- Francisco Javier Carmona

simbolosPropConj :: [Prop] -> [Prop]
simbolosPropConj s = unionGeneral (map simbolosPropForm s)

-- Luis Palma Blanco

-- ---------------------------------------------------------------------
-- Interpretaciones de un conjunto de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 17: Definir la función
-- interpretacionesConjunto :: [Prop] -> [Interpretación]
-- tal que (interpretacionesConjunto s) es la lista de las
-- interpretaciones de s. Por ejemplo,
-- interpretacionesConjunto [p --> q, q --> r]
-- ==> [[p,q,r],[p,q],[p,r],[p],[q,r],[q],[r],[]]
-- ---------------------------------------------------------------------

interpretacionesConjunto :: [Prop] -> [Interpretación]
interpretacionesConjunto = subconjuntos . símbolosPropConj

-- Elisa Mazuelos Jiménez

-- ---------------------------------------------------------------------
-- Modelos de conjuntos de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 18: Definir la función
-- esModeloConjunto :: Interpretación -> [Prop] -> Bool
-- tal que (esModeloConjunto i s) se verifica si i es modelo de s. Por
-- ejemplo,
-- esModeloConjunto [p,r] [(p \/ q) /\ ((no q) \/ r), q --> r]
-- ==> True
-- esModeloConjunto [p,r] [(p \/ q) /\ ((no q) \/ r), r --> q]
-- ==> False
-- ---------------------------------------------------------------------

esModeloConjunto :: InterpretaciÃ³n -> [Prop] -> Bool
esModeloConjunto i s = elem False xs == False
where xs = [esModeloFormula i f | f<-s]

--Javier Rodriguez Vivas

-- Comentario: la definición se puede mejorar.

esModeloConjunto :: Interpretacion -> [Prop] -> Bool
esModeloConjunto i s = and [esModeloFormula i f| f<-s]

--María Dolores Mateo Ceballos

esModeloConjunto :: Interpretacion -> [Prop] -> Bool
esModeloConjunto i s = aux i s
where aux i [] = True
aux i (x:xs) = esModeloFormula i x &&
esModeloConjunto i xs

-- Francisco Javier Carmona

-- Jaime Alberto
esModeloConjunto :: Interpretacion -> [Prop] -> Bool
esModeloConjunto i [f] = esModeloFormula i f
esModeloConjunto i (x:xs) | esModeloFormula i x = esModeloConjunto i xs
| otherwise = False

-- ---------------------------------------------------------------------
-- Ejercicio 19: Definir la función
-- modelosConjunto :: [Prop] -> [Interpretación]
-- tal que (modelosConjunto s) es la lista de modelos del conjunto
-- s. Por ejemplo,
-- modelosConjunto [(p \/ q) /\ ((no q) \/ r), q --> r]
-- ==> [[p,q,r],[p,r],[p],[q,r]]
-- modelosConjunto [(p \/ q) /\ ((no q) \/ r), r --> q]
-- ==> [[p,q,r],[p],[q,r]]
-- ---------------------------------------------------------------------

modelosConjunto :: [Prop] -> [Interpretación]
modelosConjunto s = [x|x<-interpretacionesConjunto s, esModeloConjunto x s]
--Emilio Martinez Rivero
-- ---------------------------------------------------------------------
-- Conjuntos consistentes e inconsistentes de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 20: Definir la función
-- esConsistente :: [Prop] -> Bool
-- tal que (esConsistente s) se verifica si s es consistente. Por
-- ejemplo,
-- esConsistente [(p \/ q) /\ ((no q) \/ r), p --> r]
-- ==> True
-- esConsistente [(p \/ q) /\ ((no q) \/ r), p --> r, no r]
-- ==> False
-- ---------------------------------------------------------------------

esConsistente :: [Prop] -> Bool
esConsistente s = or [esModeloConjunto x s | x <- (modelosConjunto s)]

-- Elisa Mazuelos Jiménez

-- Comentario: La definición se puede mejorar.

esConsistente :: [Prop] -> Bool
esConsistente s = modelosConjunto s /= []

-- Francisco Javier Carmona

-- ---------------------------------------------------------------------
-- Ejercicio 21: Definir la función
-- esInconsistente :: [Prop] -> Bool
-- tal que (esInconsistente s) se verifica si s es inconsistente. Por
-- ejemplo,
-- esInconsistente [(p \/ q) /\ ((no q) \/ r), p --> r]
-- ==> False
-- esInconsistente [(p \/ q) /\ ((no q) \/ r), p --> r, no r]
-- ==> True
-- ---------------------------------------------------------------------

esInconsistente :: [Prop] -> Bool
esInconsistente = not . esConsistente

-- Elisa Mazuelos Jiménez

esInconsistente :: [Prop] -> Bool
esInconsistente s = null (modelosConjunto s)

-- María Dolores Mateo Ceballos

esInconsistente :: [Prop] -> Bool
esInconsistente s = modelosConjunto s == []

-- Francisco Javier Carmona

-- ---------------------------------------------------------------------
-- Consecuencia lógica --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 22: Definir la función
-- esConsecuencia :: [Prop] -> Prop -> Bool
-- tal que (esConsecuencia s f) se verifica si f es consecuencia de
-- s. Por ejemplo,
-- esConsecuencia [p --> q, q --> r] (p --> r) ==> True
-- esConsecuencia [p] (p /\ q) ==> False
-- ---------------------------------------------------------------------

esConsecuencia :: [Prop] -> Prop -> Bool
esConsecuencia s f = and [esModeloFórmula x f| x<-modelosConjunto s]

--Emilio Martinez Rivero

-- Comentario: la definición no es correcta.

esConsecuencia :: [Prop] -> Prop -> Bool
esConsecuencia s f = esInconsistente ((no f):s)

--María Dolores Mateo Ceballos

esConsecuencia :: [Prop] -> Prop -> Bool
esConsecuencia s f = or [elem x (modelosConjunto s)| x<-(modelosFormula f)]

-- Luis Palma Blanco

</source>

Relación 1

2015-02-09T23:09:54Z

Nikdro:

<source lang = "haskell">
-- LMF 2014-15: Rel_1.hs (9 de Febrero de 2015)
-- 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 x y z = (x+y+z)/3

Miriam R.

-- ---------------------------------------------------------------------
-- 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 x = rem x 10

Miriam R.

-- ---------------------------------------------------------------------
-- 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 n xs= (drop n xs) ++ (take n xs)

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 x = if x then False else True
xor_2 False x = if x then True else False

Pablo José Gerlach Mena

--Realizado por Nikola Drousie:

xor_2' True x = not x
xor_2' False x = x

-- ---------------------------------------------------------------------
-- 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 x y = (x && (not y)) || ((not x) && y)

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 x y = x /= y

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 n = sum [x^2 | x <- [1..n]]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], x^2+y^2 == z^2]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 n = [x | x <- [1..n], esPerfecto x]

Definimos las funciones auxiliares:

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

esPerfecto :: Int -> Bool
esPerfecto n = sum (factores n) == 2*n

También podríamos definirla como:

perfectos2 :: Int -> [Int]
perfectos2 n = filter (esPerfecto) [1..n]

Podemos comprobar que ambas definiciones son equivalentes:

prop_perfectos n = perfectos n == perfectos2 n

Si queremos podemos comparar ambos algoritmos:

*Main> perfectos 500
[6,28,496]
(1.44 secs, 15935120 bytes)

*Main> perfectos2 500
[6,28,496]
(0.22 secs, 14803544 bytes)

Es decir, el segundo es más eficiente.

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 = [x+y | (x,y) <- zip xs (tail xs)]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 xs ys = length (distanciaAux xs ys)

Definimos la función auxiliar:

distanciaAux :: Eq a => [a] -> [a] -> [Int]
distanciaAux xs [] = []
distanciaAux [] ys = []
distanciaAux (x:xs) (y:ys) | x == y =distanciaAux xs ys
| otherwise =[1]++(distanciaAux xs ys)

Pablo José Gerlach Mena

-- Realizado por Nikola Drousie:

distancia' :: Eq a => [a] -> [a] -> Int
distancia' xs ys = sum [ 1 | (a,b)<-zip xs ys, a/=b]

-- ---------------------------------------------------------------------
-- 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]++[product [1..n] | n <-[1..]]

Pablo José Gerlach Mena

-- Usando zipWith:

factoriales2 :: [Integer]
factoriales2 = [1]++(zipWith f [1..] [2..])
where f n y = product ([1..n]++[y])

Emilio Martinez

-- Por recursiÃ³n:

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

Emilio Martinez

-- Usando scanl1:

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

Emilio Martinez

-- Usando iterate:

factoriales5 :: [Integer]
factoriales5 = undefined

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

*Main> take 10 factoriales1
[1,1,2,6,24,120,720,5040,40320,362880]

(0.02 secs, 0 bytes)

*Main> take 10 factoriales2
[1,2,6,24,120,720,5040,40320,362880,3628800]
(0.00 secs, 0 bytes)

*Main> take 10 factoriales3
[1,1,2,6,24,120,720,5040,40320,362880]
(0.00 secs, 528020 bytes)

*Main> take 10 factoriales4
[1,1,2,6,24,120,720,5040,40320,362880]
(0.00 secs, 0 bytes)

Pablo José Gerlach Mena

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

--Emilio Martinez

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

prop_espejo :: Arbol Int -> Bool
prop_espejo n = (espejo . espejo) n == n

-- quickCheck prop_espejo
-- +++ OK passed 100 tests.

-- Emilio Martinez
-- ---------------------------------------------------------------------
-- 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: Hoja]

espejo (espejo Hoja) = espejo (Hoja) por definicion de espejo Hoja
espejo (Hoja) = Hoja por definicion de espejo Hoja

Luego espejo (espejo Hoja)= Hoja
qed

[Suponemos que espejo (espejo x) = x , para todo x arbol]

[Sea N a i d con i, d arboles]

espejo (espejo (N a i d))= espejo (N a (espejo d) (espejo i)) por def
espejo (N a (espejo d)(espejo i)) = N a (espejo (espejo i))
(espejo(espejo
d)) por def

como i, d son arboles por hipótesis de induccion

= N a (espejo (espejo i)) (espejo (espejo d))
= N a i d

Luego espejo (espejo (N a i d)) = N a i d.
qed

Emilio Martinez
-}

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

--Emilio Martinez

-- ---------------------------------------------------------------------
-- 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 ++ [a]++ postorden d

-- Realizado por Nikola Drousie:

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

-- La propiedad es
prop_recorrido :: Arbol Int -> Bool
prop_recorrido x = (postorden . espejo) x == (reverse . postorden) x

-- La comprobaciÃ³n es
--quickCheck prop_recorrido
-- +++ OK, passed 100 tests.

--Emilio Martinez Rivero

-- ---------------------------------------------------------------------
-- 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 _ i d)= 1+(nNodos i)+(nNodos d)

--Emilio Martinez

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

-- La comprobaciÃ³n es

-- quickCheck prop_nNodos_espejo
-- +++ OK, passed 100 tests.

--Emilio Martinez

-- ---------------------------------------------------------------------
-- 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 Hoja = 0
profundidad (Nodo _ i d) = 1+ max(profundidad i) (profundidad d)

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

</source>

Relación 1

2015-02-09T22:46:35Z

Nikdro:

<source lang = "haskell">
-- LMF 2014-15: Rel_1.hs (9 de Febrero de 2015)
-- 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 x y z = (x+y+z)/3

Miriam R.

-- ---------------------------------------------------------------------
-- 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 x = rem x 10

Miriam R.

-- ---------------------------------------------------------------------
-- 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 n xs= (drop n xs) ++ (take n xs)

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 x = if x then False else True
xor_2 False x = if x then True else False

Pablo José Gerlach Mena

--Realizado por Nikola Drousie:

xor_2' True x = not x
xor_2' False x = x

-- ---------------------------------------------------------------------
-- 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 x y = (x && (not y)) || ((not x) && y)

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 x y = x /= y

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 n = sum [x^2 | x <- [1..n]]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], x^2+y^2 == z^2]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 n = [x | x <- [1..n], esPerfecto x]

Definimos las funciones auxiliares:

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

esPerfecto :: Int -> Bool
esPerfecto n = sum (factores n) == 2*n

También podríamos definirla como:

perfectos2 :: Int -> [Int]
perfectos2 n = filter (esPerfecto) [1..n]

Podemos comprobar que ambas definiciones son equivalentes:

prop_perfectos n = perfectos n == perfectos2 n

Si queremos podemos comparar ambos algoritmos:

*Main> perfectos 500
[6,28,496]
(1.44 secs, 15935120 bytes)

*Main> perfectos2 500
[6,28,496]
(0.22 secs, 14803544 bytes)

Es decir, el segundo es más eficiente.

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 = [x+y | (x,y) <- zip xs (tail xs)]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 xs ys = length (distanciaAux xs ys)

Definimos la función auxiliar:

distanciaAux :: Eq a => [a] -> [a] -> [Int]
distanciaAux xs [] = []
distanciaAux [] ys = []
distanciaAux (x:xs) (y:ys) | x == y =distanciaAux xs ys
| otherwise =[1]++(distanciaAux xs ys)

Pablo José Gerlach Mena

-- Realizado por Nikola Drousie:

distancia' :: Eq a => [a] -> [a] -> Int
distancia' xs ys = sum [ 1 | (a,b)<-zip xs ys, a/=b]

-- ---------------------------------------------------------------------
-- 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]++[product [1..n] | n <-[1..]]

Pablo José Gerlach Mena

-- Usando zipWith:

factoriales2 :: [Integer]
factoriales2 = [1]++(zipWith f [1..] [2..])
where f n y = product ([1..n]++[y])

Emilio Martinez

-- Por recursiÃ³n:

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

Emilio Martinez

-- Usando scanl1:

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

Emilio Martinez

-- Usando iterate:

factoriales5 :: [Integer]
factoriales5 = undefined

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

*Main> take 10 factoriales1
[1,1,2,6,24,120,720,5040,40320,362880]

(0.02 secs, 0 bytes)

*Main> take 10 factoriales2
[1,2,6,24,120,720,5040,40320,362880,3628800]
(0.00 secs, 0 bytes)

*Main> take 10 factoriales3
[1,1,2,6,24,120,720,5040,40320,362880]
(0.00 secs, 528020 bytes)

*Main> take 10 factoriales4
[1,1,2,6,24,120,720,5040,40320,362880]
(0.00 secs, 0 bytes)

Pablo José Gerlach Mena

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

--Emilio Martinez

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

prop_espejo :: Arbol Int -> Bool
prop_espejo n = (espejo . espejo) n == n

-- quickCheck prop_espejo
-- +++ OK passed 100 tests.

-- Emilio Martinez
-- ---------------------------------------------------------------------
-- 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: Hoja]

espejo (espejo Hoja) = espejo (Hoja) por definicion de espejo Hoja
espejo (Hoja) = Hoja por definicion de espejo Hoja

Luego espejo (espejo Hoja)= Hoja
qed

[Suponemos que espejo (espejo x) = x , para todo x arbol]

[Sea N a i d con i, d arboles]

espejo (espejo (N a i d))= espejo (N a (espejo d) (espejo i)) por def
espejo (N a (espejo d)(espejo i)) = N a (espejo (espejo i))
(espejo(espejo
d)) por def

como i, d son arboles por hipótesis de induccion

= N a (espejo (espejo i)) (espejo (espejo d))
= N a i d

Luego espejo (espejo (N a i d)) = N a i d.
qed

Emilio Martinez
-}

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

--Emilio Martinez

-- ---------------------------------------------------------------------
-- 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 ++ [a]++ postorden d

-- ---------------------------------------------------------------------
-- Ejercicio 13.6. Comprobar con QuickCheck que para todo Ã¡rbol x,
-- postorden (espejo x) = reverse (postorden x)
-- ---------------------------------------------------------------------

-- La propiedad es
prop_recorrido :: Arbol Int -> Bool
prop_recorrido x = (postorden . espejo) x == (reverse . postorden) x

-- La comprobaciÃ³n es
--quickCheck prop_recorrido
-- +++ OK, passed 100 tests.

--Emilio Martinez Rivero

-- ---------------------------------------------------------------------
-- 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 _ i d)= 1+(nNodos i)+(nNodos d)

--Emilio Martinez

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

-- La comprobaciÃ³n es

-- quickCheck prop_nNodos_espejo
-- +++ OK, passed 100 tests.

--Emilio Martinez

-- ---------------------------------------------------------------------
-- 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 Hoja = 0
profundidad (Nodo _ i d) = 1+ max(profundidad i) (profundidad d)

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

</source>

Relación 1

2015-02-09T22:13:23Z

Nikdro:

<source lang = "haskell">
-- LMF 2014-15: Rel_1.hs (9 de Febrero de 2015)
-- 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 x y z = (x+y+z)/3

Miriam R.

-- ---------------------------------------------------------------------
-- 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 x = rem x 10

Miriam R.

-- ---------------------------------------------------------------------
-- 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 n xs= (drop n xs) ++ (take n xs)

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 x = if x then False else True
xor_2 False x = if x then True else False

Pablo José Gerlach Mena

--Realizado por Nikola Drousie:

xor_2 True x = not x
xor_2 False x = x

-- ---------------------------------------------------------------------
-- 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 x y = (x && (not y)) || ((not x) && y)

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 x y = x /= y

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 n = sum [x^2 | x <- [1..n]]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], x^2+y^2 == z^2]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 n = [x | x <- [1..n], esPerfecto x]

Definimos las funciones auxiliares:

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

esPerfecto :: Int -> Bool
esPerfecto n = sum (factores n) == 2*n

También podríamos definirla como:

perfectos2 :: Int -> [Int]
perfectos2 n = filter (esPerfecto) [1..n]

Podemos comprobar que ambas definiciones son equivalentes:

prop_perfectos n = perfectos n == perfectos2 n

Si queremos podemos comparar ambos algoritmos:

*Main> perfectos 500
[6,28,496]
(1.44 secs, 15935120 bytes)

*Main> perfectos2 500
[6,28,496]
(0.22 secs, 14803544 bytes)

Es decir, el segundo es más eficiente.

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

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

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 = [x+y | (x,y) <- zip xs (tail xs)]

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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 xs ys = length (distanciaAux xs ys)

Definimos la función auxiliar:

distanciaAux :: Eq a => [a] -> [a] -> [Int]
distanciaAux xs [] = []
distanciaAux [] ys = []
distanciaAux (x:xs) (y:ys) | x == y =distanciaAux xs ys
| otherwise =[1]++(distanciaAux xs ys)

Pablo José Gerlach Mena

-- ---------------------------------------------------------------------
-- 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]++[product [1..n] | n <-[1..]]

Pablo José Gerlach Mena

-- Usando zipWith:

factoriales2 :: [Integer]
factoriales2 = [1]++(zipWith f [1..] [2..])
where f n y = product ([1..n]++[y])

Emilio Martinez

-- Por recursiÃ³n:

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

Emilio Martinez

-- Usando scanl1:

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

Emilio Martinez

-- Usando iterate:

factoriales5 :: [Integer]
factoriales5 = undefined

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

*Main> take 10 factoriales1
[1,1,2,6,24,120,720,5040,40320,362880]

(0.02 secs, 0 bytes)

*Main> take 10 factoriales2
[1,2,6,24,120,720,5040,40320,362880,3628800]
(0.00 secs, 0 bytes)

*Main> take 10 factoriales3
[1,1,2,6,24,120,720,5040,40320,362880]
(0.00 secs, 528020 bytes)

*Main> take 10 factoriales4
[1,1,2,6,24,120,720,5040,40320,362880]
(0.00 secs, 0 bytes)

Pablo José Gerlach Mena

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

--Emilio Martinez

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

prop_espejo :: Arbol Int -> Bool
prop_espejo n = (espejo . espejo) n == n

-- quickCheck prop_espejo
-- +++ OK passed 100 tests.

-- Emilio Martinez
-- ---------------------------------------------------------------------
-- 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: Hoja]

espejo (espejo Hoja) = espejo (Hoja) por definicion de espejo Hoja
espejo (Hoja) = Hoja por definicion de espejo Hoja

Luego espejo (espejo Hoja)= Hoja
qed

[Suponemos que espejo (espejo x) = x , para todo x arbol]

[Sea N a i d con i, d arboles]

espejo (espejo (N a i d))= espejo (N a (espejo d) (espejo i)) por def
espejo (N a (espejo d)(espejo i)) = N a (espejo (espejo i))
(espejo(espejo
d)) por def

como i, d son arboles por hipótesis de induccion

= N a (espejo (espejo i)) (espejo (espejo d))
= N a i d

Luego espejo (espejo (N a i d)) = N a i d.
qed

Emilio Martinez
-}

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

--Emilio Martinez

-- ---------------------------------------------------------------------
-- 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 ++ [a]++ postorden d

-- ---------------------------------------------------------------------
-- Ejercicio 13.6. Comprobar con QuickCheck que para todo Ã¡rbol x,
-- postorden (espejo x) = reverse (postorden x)
-- ---------------------------------------------------------------------

-- La propiedad es
prop_recorrido :: Arbol Int -> Bool
prop_recorrido x = (postorden . espejo) x == (reverse . postorden) x

-- La comprobaciÃ³n es
--quickCheck prop_recorrido
-- +++ OK, passed 100 tests.

--Emilio Martinez Rivero

-- ---------------------------------------------------------------------
-- 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 _ i d)= 1+(nNodos i)+(nNodos d)

--Emilio Martinez

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

-- La comprobaciÃ³n es

-- quickCheck prop_nNodos_espejo
-- +++ OK, passed 100 tests.

--Emilio Martinez

-- ---------------------------------------------------------------------
-- 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 Hoja = 0
profundidad (Nodo _ i d) = 1+ max(profundidad i) (profundidad d)

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

</source>