Valor de una expresión aritmética básica
Usando el tipo de las expresiones aritméticas básicas, definir la función
valor :: Expr -> Int
tal que valor e es el valor de la expresión aritmética e. Por ejemplo,
valor (P (C 2) (S (C 3) (C 7))) == 20
El tipo de las expresiones aritméticas básicas
1. El tipo de las expresiones aritméticas básicas en Haskell
La expresión aritmética 2*(3+7) se representa por
P (C 2) (S (C 3) (C 7))
usando el tipo de dato definido a continuación.
module Expresion_aritmetica_basica where data Expr = C Int | S Expr Expr | P Expr Expr
2. El tipo de las expresiones aritméticas básicas en Python
La expresión aritmética 2*(3+7) se representa por
P(C(2), S(C(3), C(7)))
usando el tipo de dato definido a continuación.
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class C(Expr): x: int @dataclass class S(Expr): x: Expr y: Expr @dataclass class P(Expr): x: Expr y: Expr
Valor de un árbol booleano
Se consideran los árboles con operaciones booleanas definidos por
data Arbol = H Bool | Conj Arbol Arbol | Disy Arbol Arbol | Neg Arbol
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:: Arbol ej1 = Conj (Disy (Conj (H True) (H False)) (Neg (H False))) (Conj (Neg (H False)) (H True)) ej2 = Conj (Disy (Conj (H True) (H False)) (Neg (H True))) (Conj (Neg (H False)) (H True))
Definir la función
valor :: Arbol -> Bool
tal que valor a) es el resultado de procesar el árbol a realizando las operaciones booleanas especificadas en los nodos. Por ejemplo,
valor ej1 == True valor ej2 == False
Árbol de factorización
Los divisores medios de un número son los que ocupan la 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. Para los números que son cuadrados perfectos, sus divisores medios de son sus raíces cuadradas; por ejemplos, los divisores medios de 9 son 3 y 3.
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 -> Arbol
tal que arbolFactorizacion n es el árbol de factorización de n. Por ejemplo,
arbolFactorizacion 60 == N 60 (N 6 (H 2) (H 3)) (N 10 (H 2) (H 5)) arbolFactorizacion 45 == N 45 (H 5) (N 9 (H 3) (H 3)) arbolFactorizacion 7 == H 7 arbolFactorizacion 9 == N 9 (H 3) (H 3) arbolFactorizacion 14 == N 14 (H 2) (H 7) arbolFactorizacion 28 == N 28 (N 4 (H 2) (H 2)) (H 7) arbolFactorizacion 84 == N 84 (H 7) (N 12 (H 3) (N 4 (H 2) (H 2)))
Elementos del nivel k de un árbol
Los árboles binarios con valores en las hojas y en los nodos se definen por
data Arbol a = H a | N a (Arbol a) (Arbol a)
Por ejemplo, el árbol
7 / \ / \ 2 9 / \ 5 4
se representa por
N 7 (N 2 (H 5) (H 4)) (H 9)
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 -> Arbol a -> [a]
tal que nivel k a es la lista de los elementos de nivel k del árbol a. Por ejemplo,
nivel 0 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [7] nivel 1 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [2,9] nivel 2 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [5,4] nivel 3 (N 7 (N 2 (H 5) (H 4)) (H 9)) == []
Existencia de elementos del árbol que verifican una propiedad
Los árboles binarios con valores en las hojas y en los nodos se definen por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Por ejemplo, el árbol
5 / \ / \ 3 2 / \ 1 4
se representa por
N 5 (N 3 (H 1) (H 4)) (H 2)
Definir la función
algunoArbol :: Arbol 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 (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4) == True algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7) == False
Árboles con igual estructura
Los árboles binarios con valores en las hojas y en los nodos se definen por
data Arbol a = H a | N a (Arbol a) (Arbol 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 :: Arbol Int ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8)) ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2)) ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2) ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))
Definir la función
igualEstructura :: Arbol -> Arbol -> Bool
tal que igualEstructura a1 a2 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
Árboles con bordes iguales
Los árboles binarios con valores en las hojas se pueden definir por
data Arbol a = H a | N (Arbol a) (Arbol 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 :: Arbol Int arbol1 = N (H 1) (N (H 2) (H 3)) arbol2 = N (N (H 1) (H 2)) (H 3) arbol3 = N (N (H 1) (H 4)) (H 3) arbol4 = N (N (H 2) (H 3)) (H 1)
Definir la función
igualBorde :: Eq a => Arbol a -> Arbol 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
Árboles balanceados
Los árboles binarios con valores en los nodos se pueden definir por
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq)
Por ejemplo, el árbol
9 / \ / \ 8 6 / \ / \ 3 2 4 5
se puede representar por
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
Diremos que un árbol está balanceado si para cada nodo la diferencia entre el número de nodos de sus subárboles izquierdo y derecho es menor o igual que uno.
Definir la función
balanceado :: Arbol a -> Bool
tal que (balanceado a) se verifica si el árbol a está balanceado. Por ejemplo,
λ> balanceado (N 5 H (N 3 H H)) True λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H)))) False
Rama izquierda de un árbol binario.
Los árboles binarios con valores en los nodos se pueden definir por
data Arbol a = H | N a (Arbol1 a) (Arbol1 a) deriving (Show, Eq)
Por ejemplo, el árbol
9 / \ / \ 8 6 / \ / \ 3 2 4 5
se puede representar por
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
Definir la función
ramaIzquierda :: Arbol a -> [a]
tal que ramaIzquierda a es la lista de los valores de los nodos de la rama izquierda del árbol a. Por ejemplo,
λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) [2,5,3] <!-- TEASER_END -->~~~ # Soluciones A continuación se muestran las [soluciones en Haskell](#haskell) y las [soluciones en Python](#python). <a name="haskell"></a> ## Soluciones en Haskell ~~~haskell data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) ramaIzquierda :: Arbol a -> [a] ramaIzquierda H = [] ramaIzquierda (N x i _) = x : ramaIzquierda i
Soluciones en Python
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): pass @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def ramaIzquierda(a: Arbol[A]) -> list[A]: match a: case H(): return [] case N(x, i, _): return [x] + ramaIzquierda(i) assert False