-- I1M 2021-22: Relación 13 solución
-- 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 H1 = 0
sumaArbol (N1 x i d) = x + sumaArbol i + sumaArbol 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 _ H1 = H1
mapArbol f (N1 x i d) = N1 (f x) (mapArbol f i) (mapArbol 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 H1 = []
ramaIzquierda (N1 x i _) = x : ramaIzquierda 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
-- ---------------------------------------------------------------------
balanceado :: Arbol1 a -> Bool
balanceado H1 = True
balanceado (N1 _ i d) = (abs (numeroNodos i - numeroNodos d) <= 1)
&& balanceado i && balanceado d
-- (numeroNodos a) es el número de nodos del árbol a. Por ejemplo,
-- numeroNodos (N1 5 H1 (N1 3 H1 H1)) == 2
numeroNodos :: Arbol1 a -> Int
numeroNodos H1 = 0
numeroNodos (N1 _ i d) = 1 + numeroNodos i + numeroNodos d
-- ---------------------------------------------------------------------
-- 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)
igualBorde :: Eq a => Arbol2 a -> Arbol2 a -> Bool
igualBorde t1 t2 = borde t1 == borde t2
-- (borde t) es el borde del árbol t; es decir, la lista de las hojas
-- del árbol t leídas de izquierda a derecha. Por ejemplo,
-- borde arbol4 == [2,3,1]
borde :: Arbol2 a -> [a]
borde (N2 i d) = borde i ++ borde d
borde (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, Eq)
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))
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
-- ---------------------------------------------------------------------
-- 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,
-- algunoArbol (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>4) == True
-- algunoArbol (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>7) == False
-- ---------------------------------------------------------------------
algunoArbol :: Arbol3 a -> (a -> Bool) -> Bool
algunoArbol (H3 x) p = p x
algunoArbol (N3 x i d) p = p x || algunoArbol i p || algunoArbol 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)) == []
-- ---------------------------------------------------------------------
nivel :: Int -> Arbol3 a -> [a]
nivel 0 (H3 x) = [x]
nivel 0 (N3 x _ _) = [x]
nivel _ (H3 _ ) = []
nivel k (N3 _ i d) = nivel (k-1) i ++ nivel (k-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 9 == N3 9 (H3 3) (H3 3)
-- 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)))
-- ---------------------------------------------------------------------
-- 1Ş definición
-- =============
arbolFactorizacion :: Int -> Arbol3 Int
arbolFactorizacion n
| esPrimo n = H3 n
| otherwise = N3 n (arbolFactorizacion x) (arbolFactorizacion y)
where (x,y) = divisoresMedio n
-- (esPrimo n) se verifica si n es primo. Por ejemplo,
-- esPrimo 7 == True
-- esPrimo 9 == False
esPrimo :: Int -> Bool
esPrimo n = divisores n == [1,n]
-- (divisoresMedio n) es el par formado por los divisores medios de
-- n. Por ejemplo,
-- divisoresMedio 30 == (5,6)
-- divisoresMedio 7 == (1,7)
-- divisoresMedio 16 == (4,4)
divisoresMedio :: Int -> (Int,Int)
divisoresMedio n = (n `div` x,x)
where xs = divisores n
x = xs !! (length xs `div` 2)
-- (divisores n) es la lista de los divisores de n. Por ejemplo,
-- divisores 30 == [1,2,3,5,6,10,15,30]
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `rem` x == 0]
-- 2Ş definición
-- =============
arbolFactorizacion2 :: Int -> Arbol3 Int
arbolFactorizacion2 n
| x == 1 = H3 n
| otherwise = N3 n (arbolFactorizacion x) (arbolFactorizacion y)
where (x,y) = divisoresMedio n
-- (divisoresMedio2 n) es el par formado por los divisores medios de
-- n. Por ejemplo,
-- divisoresMedio2 30 == (5,6)
-- divisoresMedio2 7 == (1,7)
divisoresMedio2 :: Int -> (Int,Int)
divisoresMedio2 n = (n `div` x,x)
where m = ceiling (sqrt (fromIntegral n))
x = head [y | y <- [m..n], n `rem` y == 0]
-- ---------------------------------------------------------------------
-- 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))
valorB:: ArbolB -> Bool
valorB (HB x) = x
valorB (Neg a) = not (valorB a)
valorB (Conj i d) = valorB i && valorB d
valorB (Disy i d) = valorB i || valorB d
-- ---------------------------------------------------------------------
-- 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 []]]
ramifica :: ArbolG a -> ArbolG a -> (a -> Bool) -> ArbolG a
ramifica (NG x as) a2 p
| p x = NG x (as' ++ [a2])
| otherwise = NG x as'
where as' = [ramifica a a2 p | a <- as]
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
nHojasG :: ArbolG a -> Int
nHojasG (NG _ []) = 1
nHojasG (NG _ as) = sum $ map nHojasG as
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
profundidadG :: ArbolG a -> Int
profundidadG (NG _ []) = 0
profundidadG (NG _ as) = 1 + (maximum (map profundidadG as))
-- ---------------------------------------------------------------------
-- 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 []])
-- ---------------------------------------------------------------------
bin2gen :: Arbol3 a -> ArbolG a
bin2gen (H3 v) = NG v []
bin2gen (N3 v i d) = NG v [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, Eq)
valor :: Expr1 -> Int
valor (C1 x) = x
valor (S1 x y) = valor x + valor y
valor (P1 x y) = valor x * valor y
-- ---------------------------------------------------------------------
-- 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))
-- ---------------------------------------------------------------------
aplica :: (Int -> Int) -> Expr1 -> Expr1
aplica f (C1 x) = C1 (f x)
aplica f (S1 e1 e2) = S1 (aplica f e1) (aplica f e2)
aplica f (P1 e1 e2) = P1 (aplica f e1) (aplica f e2)
-- ---------------------------------------------------------------------
-- 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
valorE :: Expr2 -> Int -> Int
valorE X n = n
valorE (C2 a) _ = a
valorE (S2 e1 e2) n = valorE e1 n + valorE e2 n
valorE (P2 e1 e2) n = valorE e1 n * valorE e2 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
-- ---------------------------------------------------------------------
numVars :: Expr2 -> Int
numVars X = 1
numVars (C2 _) = 0
numVars (S2 a b) = numVars a + numVars b
numVars (P2 a b) = numVars a + numVars b
-- ---------------------------------------------------------------------
-- 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, Eq)
valor3 :: Expr3 -> [(Char,Int)] -> Int
valor3 (C3 x) _ = x
valor3 (V3 x) e = head [y | (z,y) <- e, z == x]
valor3 (S3 x y) e = valor3 x e + valor3 y e
valor3 (P3 x y) e = valor3 x e * valor3 y 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
-- ---------------------------------------------------------------------
sumas :: Expr3 -> Int
sumas (V3 _) = 0
sumas (C3 _) = 0
sumas (S3 x y) = 1 + sumas x + sumas y
sumas (P3 x y) = sumas x + sumas y
-- ---------------------------------------------------------------------
-- 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'))
-- ---------------------------------------------------------------------
sustitucion :: Expr3 -> [(Char, Int)] -> Expr3
sustitucion e [] = e
sustitucion (V3 c) ((d,n):ps) | c == d = C3 n
| otherwise = sustitucion (V3 c) ps
sustitucion (C3 n) _ = C3 n
sustitucion (S3 e1 e2) ps = S3 (sustitucion e1 ps) (sustitucion e2 ps)
sustitucion (P3 e1 e2) ps = P3 (sustitucion e1 ps) (sustitucion e2 ps)
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
reducible :: Expr3 -> Bool
reducible (C3 _) = False
reducible (V3 _) = False
reducible (S3 (C3 _) (C3 _)) = True
reducible (S3 a b) = reducible a || reducible b
reducible (P3 (C3 _) (C3 _)) = True
reducible (P3 a b) = reducible a || reducible b
-- ---------------------------------------------------------------------
-- 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)
maximo :: Expr4 -> [Int] -> (Int,[Int])
maximo e ns = (m,[n | n <- ns, valor4 e n == m])
where m = maximum [valor4 e n | n <- ns]
valor4 :: Expr4 -> Int -> Int
valor4 (C4 x) _ = x
valor4 Y n = n
valor4 (S4 e1 e2) n = valor4 e1 n + valor4 e2 n
valor4 (R4 e1 e2) n = valor4 e1 n - valor4 e2 n
valor4 (P4 e1 e2) n = valor4 e1 n * valor4 e2 n
valor4 (E4 e1 m1) n = valor4 e1 n ^ m1
-- ---------------------------------------------------------------------
-- 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
-- 1Ş definición
valorEG :: Expr5 -> Int
valorEG (C5 x) = x
valorEG (A o e1 e2) = aplica2 o (valorEG e1) (valorEG e2)
where aplica2 :: Op -> Int -> Int -> Int
aplica2 Su x y = x+y
aplica2 Re x y = x-y
aplica2 Mu x y = x*y
-- 2Ş definición
valorEG2 :: Expr5 -> Int
valorEG2 (C5 n) = n
valorEG2 (A o x y) = (sig o) (valorEG2 x) (valorEG2 y)
where sig Su = (+)
sig Mu = (*)
sig Re = (-)
-- ---------------------------------------------------------------------
-- 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
-- 1Ş solución
-- ===========
valorEV :: ExpV -> (Int,Int)
valorEV (Vec x y) = (x,y)
valorEV (Sum e1 e2) = (x1+x2,y1+y2)
where (x1,y1) = valorEV e1
(x2,y2) = valorEV e2
valorEV (Mul n e) = (n*x,n*y)
where (x,y) = valorEV e
-- 2Ş solución
-- ===========
valorEV2 :: ExpV -> (Int,Int)
valorEV2 (Vec a b) = (a, b)
valorEV2 (Sum e1 e2) = suma (valorEV2 e1) (valorEV2 e2)
valorEV2 (Mul n e1) = multiplica n (valorEV2 e1)
suma :: (Int,Int) -> (Int,Int) -> (Int,Int)
suma (a,b) (c,d) = (a+c,b+d)
multiplica :: Int -> (Int, Int) -> (Int, Int)
multiplica n (a,b) = (n*a,n*b)
-- ---------------------------------------------------------------------
-- 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)))
-- 1Ş solución (calculando los caminos)
-- ------------------------------------
-- (caminos x a) es la lista de los caminos en el árbol a desde la raíz
-- hasta las hojas x. Por ejemplo,
-- caminos 2 arb1 == [[5,2],[5,4,1,2]]
-- caminos 3 arb1 == [[5,4,1,3]]
-- caminos 1 arb1 == []
caminos :: Int -> Arbol -> [[Int]]
caminos x (H y) | x == y = [[x]]
| otherwise = []
caminos x (N i r d) = map (r:) (caminos x i ++ caminos x d)
maxLong1 :: Int -> Arbol -> Int
maxLong1 x a = maximum (0: map length (caminos x a))
-- 2Ş solución
-- -----------
maxLong2 :: Int -> Arbol -> Int
maxLong2 x a = maximum (0 : aux x a)
where aux x (H y) | x == y = [1]
| otherwise = []
aux x (N i r d) = map (+1) (aux x i ++ aux 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 Arbol a = N a [Arbol 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
-- ej1, ej2, ej3 :: Arbol Int
-- ej1 = N 1 [N 8 [],N 3 [N 4 []]]
-- ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]]
-- ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]
--
-- Definir la función
-- caminosDesdeRaiz :: Arbol a -> [[a]]
-- tal que (caminosDesdeRaiz x) es la lista de todos los caminos desde
-- la raiz. Por ejemplo,
-- caminosDesdeRaiz ej1 == [[1,8],[1,3,4]]
-- caminosDesdeRaiz ej2 == [[1,8],[1,3,4],[1,3,5],[1,3,6]]
-- caminosDesdeRaiz ej3 == [[1,8,4],[1,8,5],[1,8,6],[1,3,7]]
-- ---------------------------------------------------------------------
data Arbol a = N a [Arbol a]
deriving Show
ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 8 [],N 3 [N 4 []]]
ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]]
ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]
caminosDesdeRaiz :: Arbol a -> [[a]]
caminosDesdeRaiz (N r []) = [[r]]
caminosDesdeRaiz (N r as) = map (r:) (concatMap caminosDesdeRaiz as)
-- ---------------------------------------------------------------------
-- Ejercicio 14. (Examen 1 de septiembre de 2016)
-- ---------------------------------------------------------------------
-- Los árboles se pueden representar mediante el siguiente
-- tipo de datos
-- data Arbol a = N a [Arbol a]
-- deriving Show
-- Por ejemplo, los árboles
-- 1 3
-- / \ /|\
-- 2 3 / | \
-- | 5 4 7
-- 4 | /\
-- 6 2 1
-- se representan por
-- ej1, ej2 :: Arbol Int
-- ej1 = N 1 [N 2 [],N 3 [N 4 []]]
-- ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]
--
-- Definir la función
-- ramasLargas :: Arbol b -> [[b]]
-- tal que (ramasLargas a) es la lista de las ramas más largas del árbol
-- a. Por ejemplo,
-- ramas ej1 == [[1,3,4]]
-- ramas ej2 == [[3,5,6],[3,7,2],[3,7,1]]
-- ---------------------------------------------------------------------
data Arbol a = N a [Arbol a]
deriving Show
ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]
ramasLargas :: Arbol b -> [[b]]
ramasLargas a = [xs | xs <- todasRamas,
length xs == m]
where todasRamas = ramas a
m = maximum (map length todasRamas)
-- (ramas a) es la lista de todas las ramas del árbol a. Por ejemplo,
-- ramas ej1 == [[1,2],[1,3,4]]
-- ramas ej2 == [[3,5,6],[3,4],[3,7,2],[3,7,1]]
ramas :: Arbol b -> [[b]]
ramas (N x []) = [[x]]
ramas (N x as) = [x : xs | a <- as, xs <- ramas a]
-- 2Ş solución:
ramas2 :: Arbol b -> [[b]]
ramas2 (N x []) = [[x]]
ramas2 (N x as) = concatMap (map (x:)) (map ramas2 as)
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 2]](/WIKIS/I1M2021G2/resources/assets/logoUS.png)