En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los 3 primeros ejercicios de la relación 9 sobre tipos de dato algebraico.
Los ejercicios y su solución se muestran a continuación
-- --------------------------------------------------------------------- -- 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/i1m-18/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 -- (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 = N 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 = N 1 [N 2 [],N 3 [N 4 []]] -- ejG2 = N 3 [N 5 [N 6 []], -- N 4 [], -- N 7 [N 2 [], N 1 []]] -- ejG3 = N 3 [N 5 [N 6 []], -- N 4 [N 1 [N 2 [],N 3 [N 4 []]]], -- N 7 [N 2 [], N 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, -- ghci> ramifica ejG1 (N 8 []) (>4) -- N 1 [N 2 [],N 3 [N 4 []]] -- ghci> ramifica ejG1 (N 8 []) (>3) -- N 1 [N 2 [],N 3 [N 4 [N 8 []]]] -- ghci> ramifica ejG1 (N 8 []) (>2) -- N 1 [N 2 [],N 3 [N 4 [N 8 []],N 8 []]] -- ghci> ramifica ejG1 (N 8 []) (>1) -- N 1 [N 2 [N 8 []],N 3 [N 4 [N 8 []],N 8 []]] -- ghci> ramifica ejG1 (N 8 []) (>0) -- N 1 [N 2 [N 8 []],N 3 [N 4 [N 8 []],N 8 []],N 8 []] -- --------------------------------------------------------------------- data ArbolG a = N a [ArbolG a] deriving (Eq, Show) ejG1, ejG2, ejG3 :: ArbolG Int ejG1 = N 1 [N 2 [],N 3 [N 4 []]] ejG2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]] ejG3 = N 3 [N 5 [N 6 []], N 4 [N 1 [N 2 [],N 3 [N 4 []]]], N 7 [N 2 [], N 1 []]] ramifica :: ArbolG a -> ArbolG a -> (a -> Bool) -> ArbolG a ramifica (N x xs) a2 p | p x = N x ([ramifica a a2 p | a <- xs] ++ [a2]) | otherwise = N x [ramifica a a2 p | a <- xs] -- --------------------------------------------------------------------- -- 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) |