-- I1M 2021-22: Relación 13 (14 de enero de 2022)
-- Tipos de datos algebraicos (II).
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================
-- ---------------------------------------------------------------------
-- Introducción --
-- ---------------------------------------------------------------------
-- En esta relación se presenta ejercicios sobre distintos tipos de
-- datos algebraicos. Concretamente,
-- * Árboles binarios:
-- + Árboles binarios con valores en los nodos.
-- + Árboles binarios con valores en las hojas.
-- + Árboles binarios con valores en las hojas y en los nodos.
-- + Árboles booleanos.
-- * Árboles generales
-- * Expresiones aritméticas
-- + Expresiones aritméticas básicas.
-- + Expresiones aritméticas con una variable.
-- + Expresiones aritméticas con varias variables.
-- + Expresiones aritméticas generales.
-- + Expresiones aritméticas con tipo de operaciones.
-- * Expresiones vectoriales
--
-- Los ejercicios corresponden al tema 9 que se encuentran en
-- http://www.cs.us.es/~jalonso/cursos/temas/tema-9.html
-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Los árboles binarios con valores en los nodos se
-- pueden definir por
-- data Arbol1 a = H1
-- | N1 a (Arbol1 a) (Arbol1 a)
-- deriving (Show, Eq)
-- Por ejemplo, el árbol
-- 9
-- / \
-- / \
-- 8 6
-- / \ / \
-- 3 2 4 5
-- se puede representar por
-- N1 9 (N1 8 (N1 3 H1 H1) (N1 2 H1 H1)) (N1 6 (N1 4 H1 H1) (N1 5 H1 H1))
--
-- Definir por recursión la función
-- sumaArbol :: Num a => Arbol1 a -> a
-- tal (sumaArbol x) es la suma de los valores que hay en el árbol
-- x. Por ejemplo,
-- ghci> sumaArbol (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1))
-- 21
-- ---------------------------------------------------------------------
data Arbol1 a = H1
| N1 a (Arbol1 a) (Arbol1 a)
deriving (Show, Eq)
sumaArbol :: Num a => Arbol1 a -> a
sumaArbol = undefined
--José Manuel García, Elsa Domínguez
sumaArbol1 :: Num a => Arbol1 a -> a
sumaArbol1 (H1 ) = 0
sumaArbol1 (N1 x i d) = x + (sumaArbol1 i) + (sumaArbol1 d)
-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir la función
-- mapArbol :: (a -> b) -> Arbol1 a -> Arbol1 b
-- tal que (mapArbol f x) es el árbol que resulta de sustituir cada nodo
-- n del árbol x por (f n). Por ejemplo,
-- ghci> mapArbol (+1) (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1))
-- N1 3 (N1 6 (N1 4 H1 H1) (N1 8 H1 H1)) (N1 5 H1 H1)
-- ---------------------------------------------------------------------
mapArbol :: (a -> b) -> Arbol1 a -> Arbol1 b
mapArbol = undefined
--José Manuel García, Elsa Domínguez
mapArbol1 :: (a -> b) -> Arbol1 a -> Arbol1 b
mapArbol1 f (H1) = (H1)
mapArbol1 f (N1 x i d) = (N1 (f x) (mapArbol1 f i) (mapArbol1 f d))
-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Definir la función
-- ramaIzquierda :: Arbol1 a -> [a]
-- tal que (ramaIzquierda a) es la lista de los valores de los nodos de
-- la rama izquierda del árbol a. Por ejemplo,
-- ghci> ramaIzquierda (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1))
-- [2,5,3]
-- ---------------------------------------------------------------------
ramaIzquierda :: Arbol1 a -> [a]
ramaIzquierda = undefined
--José Manuel García, Elsa Domínguez
ramaIzquierda1 :: Arbol1 a -> [a]
ramaIzquierda1 (H1) = []
ramaIzquierda1 (N1 x i d) = x : ramaIzquierda1 (i)
-- ---------------------------------------------------------------------
-- Ejercicio 1.4. Diremos que un árbol está balanceado si para cada nodo
-- v la diferencia entre el número de nodos (con valor) de sus subárboles
-- izquierdo y derecho es menor o igual que uno.
--
-- Definir la función
-- balanceado :: Arbol1 a -> Bool
-- tal que (balanceado a) se verifica si el árbol a está balanceado. Por
-- ejemplo,
-- balanceado (N1 5 H1 (N1 3 H1 H1)) == True
-- balanceado (N1 5 H1 (N1 3 (N1 4 H1 H1) H1)) == False
-- ---------------------------------------------------------------------
-- Elsa Domínguez
balanceado :: Arbol1 a -> Bool
balanceado H1 = True
balanceado (N1 _ i d) = abs (nNodos i - nNodos d) <= 1 && balanceado i && balanceado d
nNodos (H1) = 0
nNodos (N1 _ i d) = 1 + nNodos i + nNodos d
--José Manuel García
cuantosNodos H1 = 0
cuantosNodos (N1 x i d) = 1 + (cuantosNodos i) + (cuantosNodos d)
balanceado1 :: Arbol1 a -> Bool
balanceado1 H1 = True
balanceado1 (N1 x i d) | (cuantosNodos i) - (cuantosNodos d) <= 1 =
(balanceado1 i) && (balanceado1 d)
| otherwise = False
-- ---------------------------------------------------------------------
-- Ejercicio 2. Los árboles binarios con valores en las hojas se pueden
-- definir por
-- data Arbol2 a = H2 a
-- | N2 (Arbol2 a) (Arbol2 a)
-- deriving Show
-- Por ejemplo, los árboles
-- árbol1 árbol2 árbol3 árbol4
-- o o o o
-- / \ / \ / \ / \
-- 1 o o 3 o 3 o 1
-- / \ / \ / \ / \
-- 2 3 1 2 1 4 2 3
-- se representan por
-- arbol1, arbol2, arbol3, arbol4 :: Arbol2 Int
-- arbol1 = N2 (H2 1) (N2 (H2 2) (H2 3))
-- arbol2 = N2 (N2 (H2 1) (H2 2)) (H2 3)
-- arbol3 = N2 (N2 (H2 1) (H2 4)) (H2 3)
-- arbol4 = N2 (N2 (H2 2) (H2 3)) (H2 1)
--
-- Definir la función
-- igualBorde :: Eq a => Arbol2 a -> Arbol2 a -> Bool
-- tal que (igualBorde t1 t2) se verifica si los bordes de los árboles
-- t1 y t2 son iguales. Por ejemplo,
-- igualBorde arbol1 arbol2 == True
-- igualBorde arbol1 arbol3 == False
-- igualBorde arbol1 arbol4 == False
-- ---------------------------------------------------------------------
data Arbol2 a = N2 (Arbol2 a) (Arbol2 a)
| H2 a
deriving Show
arbol1, arbol2, arbol3, arbol4 :: Arbol2 Int
arbol1 = N2 (H2 1) (N2 (H2 2) (H2 3))
arbol2 = N2 (N2 (H2 1) (H2 2)) (H2 3)
arbol3 = N2 (N2 (H2 1) (H2 4)) (H2 3)
arbol4 = N2 (N2 (H2 2) (H2 3)) (H2 1)
-- Elsa Domínguez
igualBorde :: Eq a => Arbol2 a -> Arbol2 a -> Bool
igualBorde t1 t2 = borde t1 == borde t2
borde (H2 a) = [a]
borde (N2 i d) = borde i ++ borde d
--José Manuel García
igualBorde1 :: Eq a => Arbol2 a -> Arbol2 a -> Bool
igualBorde1 t1 t2 = (listaBorde t1) == (listaBorde t2)
listaBorde (N2 i d) = (listaBorde i) ++ (listaBorde d)
listaBorde (H2 x) = [x]
-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Los árboles binarios con valores en las hojas y en los
-- nodos se definen por
-- data Arbol3 a = H3 a
-- | N3 a (Arbol3 a) (Arbol3 a)
-- deriving Show
-- Por ejemplo, los árboles
-- 5 8 5 5
-- / \ / \ / \ / \
-- / \ / \ / \ / \
-- 9 7 9 3 9 2 4 7
-- / \ / \ / \ / \ / \ / \
-- 1 4 6 8 1 4 6 2 1 4 6 2
-- se pueden representar por
-- ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol3 Int
-- ej3arbol1 = N3 5 (N3 9 (H3 1) (H3 4)) (N3 7 (H3 6) (H3 8))
-- ej3arbol2 = N3 8 (N3 9 (H3 1) (H3 4)) (N3 3 (H3 6) (H3 2))
-- ej3arbol3 = N3 5 (N3 9 (H3 1) (H3 4)) (H3 2)
-- ej3arbol4 = N3 5 (H3 4) (N3 7 (H3 6) (H3 2))
--
-- Definir la función
-- igualEstructura :: Arbol3 -> Arbol3 -> Bool
-- tal que (igualEstructura a1 a1) se verifica si los árboles a1 y a2
-- tienen la misma estructura. Por ejemplo,
-- igualEstructura ej3arbol1 ej3arbol2 == True
-- igualEstructura ej3arbol1 ej3arbol3 == False
-- igualEstructura ej3arbol1 ej3arbol4 == False
-- ---------------------------------------------------------------------
data Arbol3 a = H3 a
| N3 a (Arbol3 a) (Arbol3 a)
deriving Show
ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol3 Int
ej3arbol1 = N3 5 (N3 9 (H3 1) (H3 4)) (N3 7 (H3 6) (H3 8))
ej3arbol2 = N3 8 (N3 9 (H3 1) (H3 4)) (N3 3 (H3 6) (H3 2))
ej3arbol3 = N3 5 (N3 9 (H3 1) (H3 4)) (H3 2)
ej3arbol4 = N3 5 (H3 4) (N3 7 (H3 6) (H3 2))
-- Elsa Domínguez
igualEstructura :: Arbol3 a -> Arbol3 a -> Bool
igualEstructura (H3 _) (H3 _) = True
igualEstructura (N3 _ i1 d1) (N3 _ i2 d2) = (igualEstructura i1 i2) && (igualEstructura d1 d2)
igualEstructura _ _ = False
--José Manuel García
arbolEstructura (H3 x) = (H3 0)
arbolEstructura (N3 x i d) = (N3 0 (arbolEstructura i) (arbolEstructura d))
--Si fuera deriving (Show,Eq):
--igualEstructura1 :: Arbol3 a -> Arbol3 a -> Bool
--igualEstructura1 t1 t2 = (arbolEstructura t1) == (arbolEstructura t2)
--Pero como es deriving Show :
igualEstructura1 :: Arbol3 a -> Arbol3 a -> Bool
igualEstructura1 t1 t2 = show (arbolEstructura t1) == show (arbolEstructura t2)
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Definir la función
-- algunoArbol :: Arbol3 t -> (t -> Bool) -> Bool
-- tal que (algunoArbol a p) se verifica si algún elemento del árbol a
-- cumple la propiedad p. Por ejemplo,
-- algunoArbol3 (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>4) == True
-- algunoArbol3 (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>7) == False
-- ---------------------------------------------------------------------
algunoArbol :: Arbol3 a -> (a -> Bool) -> Bool
algunoArbol = undefined
--José Manuel García, Elsa Domínguez
algunoArbol3 :: Arbol3 a -> (a -> Bool) -> Bool
algunoArbol3 (H3 x) p = (p x)
algunoArbol3 (N3 x i d) p = (p x) || (algunoArbol3 i p) || (algunoArbol3 d p)
-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Un elemento de un árbol se dirá de nivel k si aparece
-- en el árbol a distancia k de la raíz.
--
-- Definir la función
-- nivel :: Int -> Arbol3 a -> [a]
-- tal que (nivel k a) es la lista de los elementos de nivel k del árbol
-- a. Por ejemplo,
-- nivel 0 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == [7]
-- nivel 1 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == [2,9]
-- nivel 2 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == [5,4]
-- nivel 3 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == []
-- ---------------------------------------------------------------------
-- Elsa Domínguez
nivel :: Int -> Arbol3 a -> [a]
nivel 0 (H3 a) = [a]
nivel 0 (N3 a i d) = [a]
nivel n (H3 a) = []
nivel n (N3 a i d) = nivel (n-1) i ++ nivel (n-1) d
--José Manuel García
nivel1 :: Int -> Arbol3 a -> [a]
nivel1 n (H3 x) | n == 0 = [x]
| otherwise = []
nivel1 n (N3 x i d) | n == 0 = [x]
| otherwise = (nivel1 (n-1) i) ++ (nivel1 (n-1) d)
-- ---------------------------------------------------------------------
-- Ejercicio 3.4. Los divisores medios de un número son los que ocupan
-- la posición media entre los divisores de n, ordenados de menor a
-- mayor. Por ejemplo, los divisores de 60 son
-- [1,2,3,4,5,6,10,12,15,20,30,60] y sus divisores medios son 6 y 10.
--
-- El árbol de factorización de un número compuesto n se construye de la
-- siguiente manera:
-- * la raíz es el número n,
-- * la rama izquierda es el árbol de factorización de su divisor
-- medio menor y
-- * la rama derecha es el árbol de factorización de su divisor
-- medio mayor
-- Si el número es primo, su árbol de factorización sólo tiene una hoja
-- con dicho número. Por ejemplo, el árbol de factorización de 60 es
-- 60
-- / \
-- 6 10
-- / \ / \
-- 2 3 2 5
--
-- Definir la función
-- arbolFactorizacion :: Int -> Arbol3
-- tal que (arbolFactorizacion n) es el árbol de factorización de n. Por
-- ejemplo,
-- arbolFactorizacion 60 == N3 60 (N3 6 (H3 2) (H3 3)) (N3 10 (H3 2) (H3 5))
-- arbolFactorizacion 45 == N3 45 (H3 5) (N3 9 (H3 3) (H3 3))
-- arbolFactorizacion 7 == H3 7
-- arbolFactorizacion 14 == N3 14 (H3 2) (H3 7)
-- arbolFactorizacion 28 == N3 28 (N3 4 (H3 2) (H3 2)) (H3 7)
-- arbolFactorizacion 84 == N3 84 (H3 7) (N3 12 (H3 3) (N3 4 (H3 2) (H3 2)))
-- ---------------------------------------------------------------------
-- Elsa Domínguez, Adriana Gordillo
arbolFactorizacion :: Int -> Arbol3 Int
arbolFactorizacion n | primo n = (H3 n)
| otherwise = (N3 n i d)
where i = arbolFactorizacion (divisorMedioMenor n)
d = arbolFactorizacion (divisorMedioMayor n)
divisores n = [x | x <- [1..n], rem n x == 0]
divisorMedioMenor n | even (length (divisores n)) = last (take (div (length (divisores n)) 2) (divisores n))
| otherwise = (divisores n) !! (div (length (divisores n)) 2)
divisorMedioMayor n | even (length (divisores n)) = head (drop (div (length (divisores n)) 2) (divisores n))
| otherwise = (divisores n) !! (div (length (divisores n)) 2)
primo n = length (divisores n) == 2
--José Manuel García
listaDivisores :: Integral a => a -> [a]
listaDivisores n = ([x | x<- [1..n], rem n x == 0])
cogeMedio n | (not.even) l = [last (take (1+div l 2) (listaDivisores n))]
| otherwise = [last (take (div l 2) (listaDivisores n))] ++
[last (take (1+div l 2) (listaDivisores n))]
where l = length (listaDivisores n)
arbolFactorizacion :: Int -> Arbol3 Int
arbolFactorizacion n | 2 == l = H3 n
| otherwise = ( N3 n (arbolFactorizacion (head (cogeMedio n)))
((arbolFactorizacion (last (cogeMedio n)))) )
where l = length (listaDivisores n)
-- ---------------------------------------------------------------------
-- Ejercicio 4. Se consideran los árboles con operaciones booleanas
-- definidos por
-- data ArbolB = HB Bool
-- | Conj ArbolB ArbolB
-- | Disy ArbolB ArbolB
-- | Neg ArbolB
--
-- Por ejemplo, los árboles
-- Conj Conj
-- / \ / \
-- / \ / \
-- Disy Conj Disy Conj
-- / \ / \ / \ / \
-- Conj Neg Neg True Conj Neg Neg True
-- / \ | | / \ | |
-- True False False False True False True False
--
-- se definen por
-- ej1, ej2:: ArbolB
-- ej1 = Conj (Disy (Conj (HB True) (HB False))
-- (Neg (HB False)))
-- (Conj (Neg (HB False))
-- (HB True))
--
-- ej2 = Conj (Disy (Conj (HB True) (HB False))
-- (Neg (HB True)))
-- (Conj (Neg (HB False))
-- (HB True))
--
-- Definir la función
-- valorB :: ArbolB -> Bool
-- tal que (valorB ar) es el resultado de procesar el árbol realizando
-- las operaciones booleanas especificadas en los nodos. Por ejemplo,
-- valorB ej1 == True
-- valorB ej2 == False
-- ---------------------------------------------------------------------
data ArbolB = HB Bool
| Conj ArbolB ArbolB
| Disy ArbolB ArbolB
| Neg ArbolB
ej1, ej2:: ArbolB
ej1 = Conj (Disy (Conj (HB True) (HB False))
(Neg (HB False)))
(Conj (Neg (HB False))
(HB True))
ej2 = Conj (Disy (Conj (HB True) (HB False))
(Neg (HB True)))
(Conj (Neg (HB False))
(HB True))
-- Elsa Domínguez
valorB :: ArbolB -> Bool
valorB (HB a) = a
valorB (Conj i d) = valorB i && valorB d
valorB (Disy i d) = valorB i || valorB d
valorB (Neg x) = not (valorB x)
-- ---------------------------------------------------------------------
-- Ejercicio 5. Los árboles generales se pueden representar mediante el
-- siguiente tipo de dato
-- data ArbolG a = NG a [ArbolG a]
-- deriving (Eq, Show)
-- Por ejemplo, los árboles
-- 1 3 3
-- / \ /|\ / | \
-- 2 3 / | \ / | \
-- | 5 4 7 5 4 7
-- 4 | /\ | | / \
-- 6 2 1 6 1 2 1
-- / \
-- 2 3
-- |
-- 4
-- se representan por
-- ejG1, ejG2, ejG3 :: ArbolG Int
-- ejG1 = NG 1 [NG 2 [],NG 3 [NG 4 []]]
-- ejG2 = NG 3 [NG 5 [NG 6 []],
-- NG 4 [],
-- NG 7 [NG 2 [], NG 1 []]]
-- ejG3 = NG 3 [NG 5 [NG 6 []],
-- NG 4 [NG 1 [NG 2 [],NG 3 [NG 4 []]]],
-- NG 7 [NG 2 [], NG 1 []]]
--
-- Definir la función
-- ramifica :: ArbolG a -> ArbolG a -> (a -> Bool) -> ArbolG a
-- tal que (ramifica a1 a2 p) el árbol que resulta de ańadir una copia
-- del árbol a2 a los nodos de a1 que cumplen un predicado p. Por
-- ejemplo,
-- ramifica ejG1 (NG 8 []) (>4) => NG 1 [NG 2 [],NG 3 [NG 4 []]]
-- ramifica ejG1 (NG 8 []) (>3) => NG 1 [NG 2 [],NG 3 [NG 4 [NG 8 []]]]
-- ramifica ejG1 (NG 8 []) (>2) => NG 1 [NG 2 [],NG 3 [NG 4 [NG 8 []],NG 8 []]]
-- ramifica ejG1 (NG 8 []) (>1) => NG 1 [NG 2 [NG 8 []],NG 3 [NG 4 [NG 8 []],NG 8 []]]
-- ramifica ejG1 (NG 8 []) (>0) => NG 1 [NG 2 [NG 8 []],NG 3 [NG 4 [NG 8 []],NG 8 []],NG 8 []]
-- ---------------------------------------------------------------------
data ArbolG a = NG a [ArbolG a]
deriving (Eq, Show)
ejG1, ejG2, ejG3 :: ArbolG Int
ejG1 = NG 1 [NG 2 [],NG 3 [NG 4 []]]
ejG2 = NG 3 [NG 5 [NG 6 []],
NG 4 [],
NG 7 [NG 2 [], NG 1 []]]
ejG3 = NG 3 [NG 5 [NG 6 []],
NG 4 [NG 1 [NG 2 [],NG 3 [NG 4 []]]],
NG 7 [NG 2 [], NG 1 []]]
-- Nicolás Rodríguez, Elsa Domínguez
ramifica :: ArbolG a -> ArbolG a -> (a -> Bool) -> ArbolG a
ramifica (NG a xs) x p | p a = NG a ([ramifica y x p | y <- xs] ++ [x])
| otherwise = NG a [ramifica y x p | y <- xs]
--José Manuel García
ramifica1 :: ArbolG a -> ArbolG a -> (a -> Bool) -> ArbolG a
ramifica1 (NG x xs) (a) f | (f x) = (NG x ( ([ramifica1 y a f | y <-xs ]) ++ [a] ) )
| otherwise = (NG x ([ramifica1 y a f | y <-xs ]) )
-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Definir la función
-- nHojasG :: ArbolG a -> Int
-- tal que (nHojas x) es el número de hojas del árbol x. Por ejemplo,
-- nHojasG ejG1 == 2
-- nHojasG ejG2 == 4
-- nHojasG ejG3 == 5
-- ---------------------------------------------------------------------
-- Elsa Domínguez, Nicolás Rodríguez
nHojasG :: ArbolG a -> Int
nHojasG (NG _ []) = 1
nHojasG (NG _ xs) = sum [nHojasG ys | ys <- xs]
-- ---------------------------------------------------------------------
-- Ejercicio 5.3. Definir la función
-- profundidad :: ArbolG a -> Int
-- tal que (profundidadG x) es la profundidad del árbol x. Por ejemplo,
-- profundidadG ejG1 == 2
-- profundidadG ejG2 == 2
-- profundidadG ejG3 == 4
-- ---------------------------------------------------------------------
-- Elsa Domínguez, Nicolás Rodríguez
profundidadG :: ArbolG a -> Int
profundidadG (NG _ []) = 0
profundidadG (NG _ xs) = 1 + maximum [profundidadG ys | ys <- xs]
-- ---------------------------------------------------------------------
-- Ejercicio 5.4. Definir la función
-- bin2gen :: Arbol3 a -> ArbolG a
-- tal que (bin2gen x) es la traducción del árbol x definido con el tipo
-- "Arbol3" (es decir, árbol binario) a "ArbolG" (es decir, árbol
-- genérico). Por ejemplo,
-- bin2gen (N3 9 (N3 3 (H3 2) (H3 4)) (H3 7)) == (NG 9 [NG 3 [NG 2 [],NG 4 []], NG 7 []])
-- ---------------------------------------------------------------------
-- Elsa Domínguez, Nicolás Rodríguez, Adriana Gordillo
bin2gen :: Arbol3 a -> ArbolG a
bin2gen (H3 a) = NG a []
bin2gen (N3 a i d) = NG a [bin2gen i, bin2gen d]
-- ---------------------------------------------------------------------
-- Ejercicio 6.1. Las expresiones aritméticas básicas pueden
-- representarse usando el siguiente tipo de datos
-- data Expr1 = C1 Int
-- | S1 Expr1 Expr1
-- | P1 Expr1 Expr1
-- deriving Show
-- Por ejemplo, la expresión 2*(3+7) se representa por
-- P1 (C1 2) (S1 (C1 3) (C1 7))
--
-- Definir la función
-- valor :: Expr1 -> Int
-- tal que (valor e) es el valor de la expresión aritmética e. Por
-- ejemplo,
-- valor (P1 (C1 2) (S1 (C1 3) (C1 7))) == 20
-- ---------------------------------------------------------------------
data Expr1 = C1 Int
| S1 Expr1 Expr1
| P1 Expr1 Expr1
deriving Show
-- Elsa Domínguez, Nicolás Rodríguez, Adriana Gordillo
valor :: Expr1 -> Int
valor (C1 a) = a
valor (S1 i d) = valor i + valor d
valor (P1 i d) = valor i * valor d
-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Definir la función
-- aplica :: (Int -> Int) -> Expr1 -> Expr1
-- tal que (aplica f e) es la expresión obtenida aplicando la función f
-- a cada uno de los números de la expresión e. Por ejemplo,
-- ghci> aplica (+2) (S1 (P1 (C1 3) (C1 5)) (P1 (C1 6) (C1 7)))
-- S1 (P1 (C1 5) (C1 7)) (P1 (C1 8) (C1 9))
-- ghci> aplica (*2) (S1 (P1 (C1 3) (C1 5)) (P1 (C1 6) (C1 7)))
-- S1 (P1 (C1 6) (C1 10)) (P1 (C1 12) (C1 14))
-- ---------------------------------------------------------------------
-- Elsa Domínguez, Nicolás Rodríguez, Adriana Gordillo
aplica :: (Int -> Int) -> Expr1 -> Expr1
aplica f (C1 a) = C1 (f a)
aplica f (S1 i d) = S1 (aplica f i) (aplica f d)
aplica f (P1 i d) = P1 (aplica f i) (aplica f d)
-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Las expresiones aritméticas construidas con una
-- variable (denotada por X), los números enteros y las operaciones de
-- sumar y multiplicar se pueden representar mediante el tipo de datos
-- Expr2 definido por
-- data Expr2 = X
-- | C2 Int
-- | S2 Expr2 Expr2
-- | P2 Expr2 Expr2
-- Por ejemplo, la expresión "X*(13+X)" se representa por
-- "P2 X (S2 (C2 13) X)".
--
-- Definir la función
-- valorE :: Expr2 -> Int -> Int
-- tal que (valorE e n) es el valor de la expresión e cuando se
-- sustituye su variable por n. Por ejemplo,
-- valorE (P2 X (S2 (C2 13) X)) 2 == 30
-- ---------------------------------------------------------------------
data Expr2 = X
| C2 Int
| S2 Expr2 Expr2
| P2 Expr2 Expr2
-- Elsa Domínguez
valorE :: Expr2 -> Int -> Int
valorE X n = n
valorE (C2 a) n = a
valorE (S2 i d) n = (valorE i n) + (valorE d n)
valorE (P2 i d) n = (valorE i n)*(valorE d n)
-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Definir la función
-- numVars :: Expr2 -> Int
-- tal que (numVars e) es el número de variables en la expresión e. Por
-- ejemplo,
-- numVars (C2 3) == 0
-- numVars X == 1
-- numVars (P2 X (S2 (C2 13) X)) == 2
-- ---------------------------------------------------------------------
-- Elsa Domínguez
numVars :: Expr2 -> Int
numVars X = 1
numVars (C2 _) = 0
numVars (S2 i d) = numVars i + numVars d
numVars (P2 i d) = numVars i + numVars d
-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Las expresiones aritméticas con variables pueden
-- representarse usando el siguiente tipo de datos
-- data Expr3 = C3 Int
-- | V3 Char
-- | S3 Expr3 Expr3
-- | P3 Expr3 Expr3
-- deriving Show
-- Por ejemplo, la expresión 2*(a+5) se representa por
-- P3 (C3 2) (S3 (V3 'a') (C3 5))
--
-- Definir la función
-- valor3 :: Expr3 -> [(Char,Int)] -> Int
-- tal que (valor3 x e) es el valor3 de la expresión x en el entorno e (es
-- decir, el valor3 de la expresión donde las variables de x se sustituyen
-- por los valores según se indican en el entorno e). Por ejemplo,
-- ghci> valor3 (P3 (C3 2) (S3 (V3 'a') (V3 'b'))) [('a',2),('b',5)]
-- 14
-- ---------------------------------------------------------------------
data Expr3 = C3 Int
| V3 Char
| S3 Expr3 Expr3
| P3 Expr3 Expr3
deriving Show
-- Elsa Domínguez
valor3 :: Expr3 -> [(Char,Int)] -> Int
valor3 (C3 a) _ = a
valor3 (V3 a) e = head [n | (x,n) <- e, x == a]
valor3 (S3 i d) e = (valor3 i e) + (valor3 d e)
valor3 (P3 i d) e = (valor3 i e)*(valor3 d e)
-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir la función
-- sumas :: Expr3 -> Int
-- tal que (sumas e) es el número de sumas en la expresión e. Por
-- ejemplo,
-- sumas (P3 (V3 'z') (S3 (C3 3) (V3 'x'))) == 1
-- sumas (S3 (V3 'z') (S3 (C3 3) (V3 'x'))) == 2
-- sumas (P3 (V3 'z') (P3 (C3 3) (V3 'x'))) == 0
-- ---------------------------------------------------------------------
-- Elsa Domínguez
sumas :: Expr3 -> Int
sumas (C3 _) = 0
sumas (V3 _) = 0
sumas (S3 i d) = 1 + sumas i + sumas d
sumas (P3 i d) = sumas i + sumas d
-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Definir la función
-- sustitucion :: Expr3 -> [(Char, Int)] -> Expr3
-- tal que (sustitucion e s) es la expresión obtenida sustituyendo las
-- variables de la expresión e según se indica en la sustitución s. Por
-- ejemplo,
-- ghci> sustitucion (P3 (V3 'z') (S3 (C3 3) (V3 'x'))) [('x',7),('z',9)]
-- P3 (C3 9) (S3 (C3 3) (C3 7))
-- ghci> sustitucion (P3 (V3 'z') (S3 (C3 3) (V3 'y'))) [('x',7),('z',9)]
-- P3 (C3 9) (S3 (C3 3) (V3 'y'))
-- ---------------------------------------------------------------------
-- Elsa Domínguez
sustitucion :: Expr3 -> [(Char, Int)] -> Expr3
sustitucion (C3 a) s = C3 a
sustitucion (V3 b) s | not (null [n | (x,n) <- s, x == b]) = C3 (head [n | (x,n) <- s, x == b])
| otherwise = V3 b
sustitucion (S3 i d) s = S3 (sustitucion i s) (sustitucion d s)
sustitucion (P3 i d) s = P3 (sustitucion i s) (sustitucion d s)
-- ---------------------------------------------------------------------
-- Ejercicio 8.4. Definir la función
-- reducible :: Expr3 -> Bool
-- tal que (reducible a) se verifica si a es una expresión reducible; es
-- decir, contiene una operación en la que los dos operandos son números.
-- Por ejemplo,
-- reducible (S3 (C3 3) (C3 4)) == True
-- reducible (S3 (C3 3) (V3 'x')) == False
-- reducible (S3 (C3 3) (P3 (C3 4) (C3 5))) == True
-- reducible (S3 (V3 'x') (P3 (C3 4) (C3 5))) == True
-- reducible (S3 (C3 3) (P3 (V3 'x') (C3 5))) == False
-- reducible (C3 3) == False
-- reducible (V3 'x') == False
-- ---------------------------------------------------------------------
-- Elsa Domínguez
reducible :: Expr3 -> Bool
reducible (C3 _) = False
reducible (V3 _) = False
reducible (S3 (C3 _) (C3 _)) = True
reducible (P3 (C3 _) (C3 _)) = True
reducible (S3 i d) = reducible i || reducible d
reducible (P3 i d) = reducible i || reducible d
-- ---------------------------------------------------------------------
-- Ejercicio 9. Las expresiones aritméticas generales se pueden definir
-- usando el siguiente tipo de datos
-- data Expr4 = C4 Int
-- | Y
-- | S4 Expr4 Expr4
-- | R4 Expr4 Expr4
-- | P4 Expr4 Expr4
-- | E4 Expr4 Int
-- deriving (Eq, Show)
-- Por ejemplo, la expresión
-- 3*x - (x+2)^7
-- se puede definir por
-- R4 (P4 (C4 3) Y) (E4 (S4 Y (C4 2)) 7)
--
-- Definir la función
-- maximo :: Expr4 -> [Int] -> (Int,[Int])
-- tal que (maximo e xs) es el par formado por el máximo valor de la
-- expresión e para los puntos de xs y en qué puntos alcanza el
-- máximo. Por ejemplo,
-- ghci> maximo (E4 (S4 (C4 10) (P4 (R4 (C4 1) Y) Y)) 2) [-3..3]
-- (100,[0,1])
-- ---------------------------------------------------------------------
data Expr4 = C4 Int
| Y
| S4 Expr4 Expr4
| R4 Expr4 Expr4
| P4 Expr4 Expr4
| E4 Expr4 Int
deriving (Eq, Show)
-- Elsa Domínguez
maximo :: Expr4 -> [Int] -> (Int,[Int])
maximo e ns = (maximum [valor4 e n | n <- ns], [n | n <- ns, valor4 e n == maximum [valor4 e n | n <- ns]])
valor4 (C4 a) _ = a
valor4 Y n = n
valor4 (S4 i d) n = valor4 i n + valor4 d n
valor4 (R4 i d) n = valor4 i n - valor4 d n
valor4 (P4 i d) n = (valor4 i n)*(valor4 d n)
valor4 (E4 i x) n = (valor4 i n)^x
-- ---------------------------------------------------------------------
-- Ejercicio 10. Las operaciones de suma, resta y multiplicación se
-- pueden representar mediante el siguiente tipo de datos
-- data Op = Su | Re | Mu
-- La expresiones aritméticas con dichas operaciones se pueden
-- representar mediante el siguiente tipo de dato algebraico
-- data Expr5 = C5 Int
-- | A Op Expr5 Expr
-- Por ejemplo, la expresión
-- (7-3)+(2*5)
-- se representa por
-- A Su (A Re (C5 7) (C5 3)) (A Mu (C5 2) (C5 5))
--
-- Definir la función
-- valorEG :: Expr5 -> Int
-- tal que (valorEG e) es el valorEG de la expresión e. Por ejemplo,
-- valorEG (A Su (A Re (C5 7) (C5 3)) (A Mu (C5 2) (C5 5))) == 14
-- valorEG (A Mu (A Re (C5 7) (C5 3)) (A Su (C5 2) (C5 5))) == 28
-- ---------------------------------------------------------------------
data Op = Su | Re | Mu
data Expr5 = C5 Int | A Op Expr5 Expr5
-- Elsa Domínguez
valorEG :: Expr5 -> Int
valorEG (C5 a) = a
valorEG (A Su i d) = valorEG i + valorEG d
valorEG (A Re i d) = valorEG i - valorEG d
valorEG (A Mu i d) = (valorEG i)*(valorEG d)
-- ---------------------------------------------------------------------
-- Ejercicio 11. Se consideran las expresiones vectoriales formadas por
-- un vector, la suma de dos expresiones vectoriales o el producto de un
-- entero por una expresión vectorial. El siguiente tipo de dato define
-- las expresiones vectoriales
-- data ExpV = Vec Int Int
-- | Sum ExpV ExpV
-- | Mul Int ExpV
-- deriving Show
--
-- Definir la función
-- valorEV :: ExpV -> (Int,Int)
-- tal que (valorEV e) es el valorEV de la expresión vectorial c. Por
-- ejemplo,
-- valorEV (Vec 1 2) == (1,2)
-- valorEV (Sum (Vec 1 2 ) (Vec 3 4)) == (4,6)
-- valorEV (Mul 2 (Vec 3 4)) == (6,8)
-- valorEV (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4))) == (8,12)
-- valorEV (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4))) == (8,12)
-- ---------------------------------------------------------------------
data ExpV = Vec Int Int
| Sum ExpV ExpV
| Mul Int ExpV
deriving Show
-- Elsa Domínguez
valorEV :: ExpV -> (Int,Int)
valorEV (Vec a b) = (a,b)
valorEV (Sum i d) = (fst (valorEV i) + fst (valorEV d), snd (valorEV i) + snd (valorEV d))
valorEV (Mul i d) = (i*fst (valorEV d), i*snd (valorEV d))
-- ---------------------------------------------------------------------
-- Ejercicio 12. (Examen 12 de marzo de 2015, grupo 4)
-- ---------------------------------------------------------------------
-- Consideremos los árboles binarios con etiquetas en las
-- hojas y en los nodos. Por ejemplo,
-- 5
-- / \
-- 2 4
-- / \
-- 7 1
-- / \
-- 2 3
--
-- Un camino es una sucesión de nodos desde la raiz hasta una hoja. Por
-- ejemplo, [5,2] y [5,4,1,2] son caminos que llevan a 2, mientras que
-- [5,4,1] no es un camino, pues no lleva a una hoja.
--
-- Definimos el tipo de dato Arbol y el ejemplo por
-- data Arbol = H Int | N Arbol Int Arbol
-- deriving Show
--
-- arb1:: Arbol
-- arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))
--
-- Definir la función
-- maxLong :: Int -> Arbol -> Int
-- tal que (maxLong x a) es la longitud máxima de los caminos que
-- terminan en x. Por ejemplo,
-- maxLong 3 arb1 == 4
-- maxLong 2 arb1 == 4
-- maxLong 7 arb1 == 3
-- ---------------------------------------------------------------------
data Arbol = H Int | N Arbol Int Arbol
deriving Show
arb1:: Arbol
arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))
-- Elsa Domínguez
maxLong :: Int -> Arbol -> Int
maxLong x a | not (null (caminos x a)) = maximum (map (length) (caminos x a))
| otherwise = 0
caminos x (H a) | x == a = [[a]]
| otherwise = []
caminos x (N i a d) = map (a:) (caminos x i ++ caminos x d)
-- ---------------------------------------------------------------------
-- Ejercicio 13. (Examen 5 de diciembre de 2017, grupo 1)
-- ---------------------------------------------------------------------
-- Los árboles con un número variable de sucesores se
-- pueden representar mediante el siguiente tipo de dato
-- data ArbolG a = NG a [ArbolG a]
-- deriving Show
-- Por ejemplo, los árboles
-- 1 1 1
-- / \ / \ / \
-- 8 3 8 3 8 3
-- | /|\ /|\ |
-- 4 4 5 6 4 5 6 7
-- se representan por
-- ej21, ej22, ej23 :: ArbolG Int
-- ej21 = NG 1 [NG 8 [],NG 3 [NG 4 []]]
-- ej22 = NG 1 [NG 8 [], NG 3 [NG 4 [], NG 5 [], NG 6 []]]
-- ej23 = NG 1 [NG 8 [NG 4 [], NG 5 [], NG 6 []], NG 3 [NG 7 []]]
--
-- Definir la función
-- caminosDesdeRaiz :: ArbolG a -> [[a]]
-- tal que (caminosDesdeRaiz x) es la lista de todos los caminos desde
-- la raiz. Por ejemplo,
-- caminosDesdeRaiz ej21 == [[1,8],[1,3,4]]
-- caminosDesdeRaiz ej22 == [[1,8],[1,3,4],[1,3,5],[1,3,6]]
-- caminosDesdeRaiz ej23 == [[1,8,4],[1,8,5],[1,8,6],[1,3,7]]
-- ---------------------------------------------------------------------
ej21, ej22, ej23 :: ArbolG Int
ej21 = NG 1 [NG 8 [],NG 3 [NG 4 []]]
ej22 = NG 1 [NG 8 [], NG 3 [NG 4 [], NG 5 [], NG 6 []]]
ej23 = NG 1 [NG 8 [NG 4 [], NG 5 [], NG 6 []], NG 3 [NG 7 []]]
-- Elsa Domínguez, Nicolás Rodríguez Ruiz
-- Dos versiones:
caminosDesdeRaiz :: ArbolG a -> [[a]]
caminosDesdeRaiz (NG a []) = [[a]]
caminosDesdeRaiz (NG a xs) = map (a:) (concat [(caminosDesdeRaiz x) | x <- xs])
caminosDesdeRaiz2 :: ArbolG a -> [[a]]
caminosDesdeRaiz2 (NG a []) = [[a]]
caminosDesdeRaiz2 (NG a xs) = [a:ys | y <- xs, ys <- caminosDesdeRaiz2 y]
-- ---------------------------------------------------------------------
-- Ejercicio 14. (Examen 1 de septiembre de 2016)
-- ---------------------------------------------------------------------
-- Los árboles se pueden representar mediante el siguiente
-- tipo de datos
-- data ArbolG a = NG a [ArbolG a]
-- deriving Show
-- Por ejemplo, los árboles
-- 1 3
-- / \ /|\
-- 2 3 / | \
-- | 5 4 7
-- 4 | /\
-- 6 2 1
-- se representan por
-- ej31, ej32 :: ArbolG Int
-- ej31 = NG 1 [NG 2 [],NG 3 [NG 4 []]]
-- ej32 = NG 3 [NG 5 [NG 6 []], NG 4 [], NG 7 [NG 2 [], NG 1 []]
--
-- Definir la función
-- ramasLargas :: ArbolG b -> [[b]]
-- tal que (ramasLargas a) es la lista de las ramas más largas del árbol
-- a. Por ejemplo,
-- ramas ej31 == [[1,3,4]]
-- ramas ej32 == [[3,5,6],[3,7,2],[3,7,1]]
-- ---------------------------------------------------------------------
ej31, ej32 :: ArbolG Int
ej31 = NG 1 [NG 2 [],NG 3 [NG 4 []]]
ej32 = NG 3 [NG 5 [NG 6 []], NG 4 [], NG 7 [NG 2 [], NG 1 []]]
-- Elsa Domínguez
ramasLargas :: ArbolG b -> [[b]]
ramasLargas a = [as | as <- caminosDesdeRaiz a, length as == maximum [length as | as <- caminosDesdeRaiz a]]
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 2]](/WIKIS/I1M2021G2/resources/assets/logoUS.png)