Utilizando el tipo abstracto de datos de los polinomios definir la función
derivada :: (Eq a, Num a) => Polinomio a -> Polinomio a
tal que derivada p es la derivada del polinomio p. Por ejemplo,
λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol x^5 + 5*x^2 + 4*x λ> derivada ejPol 5*x^4 + 10*x + 4
Utilizando el tipo abstracto de datos de los polinomios definir la función
esRaiz :: (Num a, Eq a) => a -> Polinomio a -> Bool
tal que esRaiz c p se verifica si c es una raiz del polinomio p. Por ejemplo,
λ> ejPol = consPol 4 6 (consPol 1 2 polCero) λ> ejPol 6*x^4 + 2*x λ> esRaiz 0 ejPol True λ> esRaiz 1 ejPol False
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
valor :: (Num a, Eq a) => Polinomio a -> a -> a
tal que valor p c es el valor del polinomio p al sustituir su variable por c. Por ejemplo,
λ> ejPol = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) λ> ejPol 3*x^4 + -5*x^2 + 3 λ> valor ejPol 0 3 λ> valor ejPol 1 1 λ> valor ejPol (-2) 31
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
tal que multPol p q es el producto de los polinomios p y q. Por ejemplo,
λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol1 3*x^4 + -5*x^2 + 3 λ> ejPol2 x^5 + 5*x^2 + 4*x λ> multPol ejPol1 ejPol2 3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x
Comprobar con QuickCheck las siguientes propiedades
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
tal que (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,
λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol1 3*x^4 + -5*x^2 + 3 λ> ejPol2 x^5 + 5*x^2 + 4*x λ> sumaPol ejPol1 ejPol2 x^5 + 3*x^4 + 4*x + 3
Comprobar con QuickCheck las siguientes propiedades:
polCero es el elemento neutro de la suma.Utilizando el tipo abstracto de datos de los polinomios definir las funciones
termLider :: (Num a, Eq a) => Polinomio a -> Polinomio a
tal que termLider p es el término líder del polinomio p. Por ejemplo,
λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol x^5 + 5*x^2 + 4*x λ> termLider ejPol x^5
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a
tal que (creaTermino n a) es el término a*x^n. Por ejemplo,
creaTermino 2 5 == 5*x^2
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a]
tales que
densaApolinomio xs es el polinomio cuya representación densa es xs. Por ejemplo,λ> densaApolinomio [9,0,0,5,0,4,7] 9*x^6 + 5*x^3 + 4*x + 7
polinomioAdensa p es la representación densa del polinomio p. Por ejemplo,λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero))) λ> ejPol 9*x^6 + 5*x^3 + 4*x + 7 λ> polinomioAdensa ejPol [9,0,0,5,0,4,7]
Comprobar con QuickCheck que ambas funciones son inversas.
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
tal que coeficiente k p es el coeficiente del término de grado k del polinomio p. Por ejemplo,
λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol x^5 + 5*x^2 + 4*x λ> coeficiente 2 ejPol 5 λ> coeficiente 3 ejPol 0
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]
tales que
dispersaApolinomio ps es el polinomiocuya representación dispersa es ps. Por ejemplo,λ> dispersaApolinomio [(6,9),(3,5),(1,4),(0,7)] 9*x^6 + 5*x^3 + 4*x + 7
polinomioAdispersa p es la representación dispersa del polinomio p. Por ejemplo,λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero))) λ> ejPol 9*x^6 + 5*x^3 + 4*x + 7 λ> polinomioAdispersa ejPol [(6,9),(3,5),(1,4),(0,7)]
Comprobar con QuickCheck que ambas funciones son inversas.
Definir las funciones
densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)] dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a]
tales que
densaAdispersa xs es la representación dispersa del polinomio cuya representación densa es xs. Por ejemplo,λ> densaAdispersa [9,0,0,5,0,4,7] [(6,9),(3,5),(1,4),(0,7)]
dispersaAdensa ps es la representación densa del polinomio cuya representación dispersa es ps. Por ejemplo,λ> dispersaAdensa [(6,9),(3,5),(1,4),(0,7)] [9,0,0,5,0,4,7]
Comprobar con QuickCheck que las funciones densaAdispersa y dispersaAdensa son inversas.
Un polinomio es una expresión matemática compuesta por una suma de términos, donde cada término es el producto de un coeficiente y una variable elevada a una potencia. Por ejemplo, el polinomio 3x^2+2x-1 tiene un término de segundo grado (3x^2), un término de primer grado (2x) y un término constante (-1).
Las operaciones que definen al tipo abstracto de datos (TAD) de los polinomios (cuyos coeficientes son del tipo a) son las siguientes:
polCero :: Polinomio a esPolCero :: Polinomio a -> Bool consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a grado :: Polinomio a -> Int coefLider :: Num a => Polinomio a -> a restoPol :: (Num a, Eq a) => Polinomio a -> Polinomio a
tales que
Por ejemplo, el polinomio
3*x^4 + -5*x^2 + 3
se representa por
consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
Las operaciones tienen que verificar las siguientes propiedades:
Usando el tipo de las relaciones binarias, definir las funciones
clausuraTransitiva :: Eq a => Rel a -> Rel a
tal que clausuraTransitiva r es la clausura transitiva de r; es
decir, la menor relación transitiva que contiene a r. Por ejemplo,
λ> clausuraTransitiva (R ([1..6],[(1,2),(2,5),(5,6)])) R ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)])
Comprobar con QuickCheck que clausuraTransitiva es transitiva.
Usando el tipo de las relaciones binarias, definir las funciones
clausuraSimetrica :: Eq a => Rel a -> Rel a
tal que clausuraSimetrica r es la clausura simétrica de r; es decir, la menor relación simétrica que contiene a r. Por ejemplo,
λ> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)])) R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)])
Comprobar con QuickCheck que clausuraSimetrica es simétrica.
Usando el tipo de las relaciones binarias, definir las funciones
clausuraReflexiva :: Eq a => Rel a -> Rel a
tal que clausuraReflexiva r es la clausura reflexiva de r; es decir, la menor relación reflexiva que contiene a r. Por ejemplo,
λ> clausuraReflexiva (R ([1,3],[(1,1),(3,1)])) R ([1,3],[(1,1),(3,1),(3,3)])
Usando el tipo de las relaciones binarias, definir las funciones
total :: Eq a => Rel a -> Bool
tal que total r se verifica si la relación r es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x está relacionado con y o y está relacionado con x. Por ejemplo,
total (R ([1,3],[(1,1),(3,1),(3,3)])) == True total (R ([1,3],[(1,1),(3,1)])) == False total (R ([1,3],[(1,1),(3,3)])) == False
Usando el tipo de las relaciones binarias, definir las funciones
antisimetrica :: Eq a => Rel a -> Bool
tal que antisimetrica r se verifica si la relación r es antisimétrica; es decir, si (x,y) e (y,x) están relacionado, entonces x=y. Por ejemplo,
antisimetrica (R ([1,2],[(1,2)])) == True antisimetrica (R ([1,2],[(1,2),(2,1)])) == False antisimetrica (R ([1,2],[(1,1),(2,1)])) == True
Usando el tipo de las relaciones binarias, definir las funciones
irreflexiva :: Eq a => Rel a -> Bool
tal que irreflexiva r se verifica si la relación r es irreflexiva; es decir, si ningún elemento de su universo está relacionado con él mismo. Por ejemplo,
irreflexiva (R ([1,2,3],[(1,2),(2,1),(2,3)])) == True irreflexiva (R ([1,2,3],[(1,2),(2,1),(3,3)])) == False
Usando el tipo de las relaciones binarias, definir las funciones
esEquivalencia :: Ord a => Rel a -> Bool
tal que esEquivalencia r se verifica si la relación r es de equivalencia. Por ejemplo,
λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) True λ> esEquivalencia (R ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) False λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,3),(5,5)])) False
Usando el tipo de las relaciones binarias, definir las funciones
transitiva :: Ord a => Rel a -> Bool
tal que transitiva r se verifica si la relación r es transitiva. Por ejemplo,
transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) == True transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(5,5)])) == False
Definir la función
subconjunto :: Ord a => [a] -> [a] -> Bool
tal que subconjunto xs ys se verifica si xs es un subconjunto de ys. Por ejemplo,
subconjunto [3,2,3] [2,5,3,5] == True subconjunto [3,2,3] [2,5,6,5] == False
Usando el tipo de las relaciones binarias, definir las funciones
composicion :: Eq a => Rel a -> Rel a -> Rel a
tal que composicion r s es la composición de las relaciones r y s. Por ejemplo,
λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)])) R ([1,2],[(1,1),(2,1)])
Usando el tipo de las relaciones binarias, definir las funciones
simetrica :: Eq a => Rel a -> Bool
tal que simetrica r se verifica si la relación r es simétrica. Por ejemplo,
simetrica (R ([1,3],[(1,1),(1,3),(3,1)])) == True simetrica (R ([1,3],[(1,1),(1,3),(3,2)])) == False simetrica (R ([1,3],[])) == True
Usando el tipo de las relaciones binarias, definir las funciones
reflexiva :: Eq a => Rel a -> Bool
tal que reflexiva r se verifica si la relación r es reflexiva. Por ejemplo,
reflexiva (R ([1,3],[(1,1),(1,3),(3,3)])) == True reflexiva (R ([1,2,3],[(1,1),(1,3),(3,3)])) == False
Usando el tipo de las relaciones binarias, definir las funciones
universo :: Eq a => Rel a -> [a] grafo :: Eq a => ([a],[(a,a)]) -> [(a,a)]
tales que
universo r es el universo de la relación r. Por ejemplo,λ> r = R ([1, 3],[(3, 1), (3, 3)]) λ> universo r [1,3]
grafo r es el grafo de la relación r. Por ejemplo,λ> grafo r [(3,1),(3,3)]
Una relación binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R).
Definir el tipo de dato (Rel a), para representar las relaciones binarias sobre a, y la función
esRelacionBinaria :: Eq a => Rel a -> Bool
tal que esRelacionBinaria r se verifica si r es una relación binaria. Por ejemplo,
λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 3)])) True λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)])) False
Además, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.
Utilizando el tipo abstracto de datos de los conjuntos definir la función
productoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)
tal que productoC c1 c2 es el producto cartesiano de los conjuntos c1 y c2. Por ejemplo,
λ> ej1 = inserta 2 (inserta 5 vacio) λ> ej2 = inserta 9 (inserta 4 (inserta 3 vacio)) λ> productoC ej1 ej2 {(2,3), (2,4), (2,9), (5,3), (5,4), (5,9)}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
algunos :: Ord a => (a -> Bool) -> Conj a -> Bool
tal que algunos p c se verifica si algún elemento de c verifica el predicado p. Por ejemplo,
algunos even (inserta 4 (inserta 7 vacio)) == True algunos even (inserta 3 (inserta 7 vacio)) == False
Utilizando el tipo abstracto de datos de los conjuntos definir la función
todos :: Ord a => (a -> Bool) -> Conj a -> Bool
tal que todos p c se verifica si todos los elemsntos de c verifican el predicado p. Por ejemplo,
todos even (inserta 4 (inserta 6 vacio)) == True todos even (inserta 4 (inserta 7 vacio)) == False
Utilizando el tipo abstracto de datos de los conjuntos definir la función
mapC :: (Ord a, Ord b) => (a -> b) -> Conj a -> Conj b
tal que map f c es el conjunto formado por las imágenes de los elementos del conjunto c, mediante la aplicación f. Por ejemplo,
λ> mapC (*2) (inserta 3 (inserta 1 vacio)) {2, 6}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
divide :: (Ord a) => a-> Conj a -> (Conj a, Conj a)
tal que divide x c es el par formado por dos subconjuntos de c: el de los elementos menores o iguales que x y el de los mayores que x. Por ejemplo,
λ> divide 5 (inserta 7 (inserta 2 (inserta 8 vacio))) ({2},{7, 8})
Utilizando el tipo abstracto de datos de los conjuntos definir la función
particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)
tal que particion c es el par formado por dos conjuntos: el de los elementos de c que verifican p y el de los elementos que no lo verifican. Por ejemplo,
λ> ej = inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))) λ> particion even ej ({2, 4},{5, 7})
Utilizando el tipo abstracto de datos de los conjuntos definir la función
filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a
tal filtra p c es el conjunto de elementos de c que verifican el predicado p. Por ejemplo,
λ> filtra even (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))) {2, 4} λ> filtra odd (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))) {5, 7}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a
tal que diferenciaSimetrica c1 c2 es la diferencia simétrica de los conjuntos c1 y c2. Por ejemplo,
λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio))) λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio)) λ> diferenciaSimetrica ej1 ej2 {2, 4, 5}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
diferencia :: Ord a => Conj a -> Conj a -> Conj a
tal que diferencia c1 c2 es el conjunto de los elementos de c1 que no son elementos de c2. Por ejemplo,
λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio))) λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio)) λ> diferencia ej1 ej2 {2, 5} λ> diferencia ej2 ej1 {4} λ> diferencia ej1 ej1 {}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
disjuntos :: Ord a => Conj a -> Conj a -> Bool
tal que disjuntos c1 c2 se verifica si los conjuntos c1 y c2 son disjuntos. Por ejemplo,
λ> ej1 = inserta 2 (inserta 5 vacio) λ> ej2 = inserta 4 (inserta 3 vacio) λ> ej3 = inserta 5 (inserta 3 vacio) λ> disjuntos ej1 ej2 True λ> disjuntos ej1 ej3 False
Utilizando el tipo abstracto de datos de los conjuntos definir la función
interseccionG :: Ord a => [Conj a] -> Conj a
tal que interseccionG cs es la intersección de la lista de conjuntos cs. Por ejemplo,
λ> ej1 = inserta 2 (inserta 3 (inserta 5 vacio)) λ> ej2 = inserta 5 (inserta 2 (inserta 7 vacio)) λ> ej3 = inserta 3 (inserta 2 (inserta 5 vacio)) λ> interseccionG [ej1, ej2, ej3] {2, 5}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
interseccion :: Ord a => Conj a -> Conj a -> Conj a
tal que interseccion c1 c2 es la intersección de los conjuntos c1 y c2. Por ejemplo,
λ> ej1 = inserta 3 (inserta 5 (inserta 2 vacio)) λ> ej2 = inserta 2 (inserta 4 (inserta 3 vacio)) λ> interseccion ej1 ej2 {2, 3}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
unionG:: Ord a => [Conj a] -> Conj a
tal unionG cs calcule la unión de la lista de conjuntos cs. Por ejemplo,
λ> ej1 = inserta 3 (inserta 5 vacio) λ> ej2 = inserta 5 (inserta 6 vacio) λ> ej3 = inserta 3 (inserta 6 vacio) λ> unionG [ej1, ej2, ej3] {3, 5, 6}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
union :: Ord a => Conj a -> Conj a -> Conj a
tal union c1 c2 es la unión de ambos conjuntos. Por ejemplo,
λ> ej1 = inserta 3 (inserta 5 vacio) λ> ej2 = inserta 4 (inserta 3 vacio) λ> union ej1 ej2 {3, 4, 5}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
cardinal :: Conj a -> Int
tal que cardinal c es el número de elementos del conjunto c. Por ejemplo,
cardinal (inserta 4 (inserta 5 vacio)) == 2 cardinal (inserta 4 (inserta 5 (inserta 4 vacio))) == 2
Utilizando el tipo abstracto de datos de los conjuntos definir la función
unitario :: Ord a => a -> Conj a
tal que unitario x es el conjunto {x}. Por ejemplo,
unitario 5 == {5}
Utilizando el tipo abstracto de datos de los conjuntos definir la función
subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool
tal subconjuntoPropio c1 c2 se verifica si c1 es un subconjunto propio de c2. Por ejemplo,
λ> ej1 = inserta 5 (inserta 2 vacio) λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio)) λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio)) λ> ej4 = inserta 2 (inserta 5 vacio) λ> subconjuntoPropio ej1 ej2 True λ> subconjuntoPropio ej1 ej3 False λ> subconjuntoPropio ej1 ej4 False
Utilizando el tipo abstracto de datos de los conjuntos definir la función
subconjunto :: Ord a => Conj a -> Conj a -> Bool
tal que subconjunto c1 c2 se verifica si todos los elementos de c1 pertenecen a c2. Por ejemplo,
λ> ej1 = inserta 5 (inserta 2 vacio) λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio)) λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio)) λ> subconjunto ej1 ej2 True λ> subconjunto ej1 ej3 False
Utilizando el tipo abstracto de datos de los conjuntos definir las funciones
listaAconjunto :: [a] -> Conj a conjuntoAlista :: Conj a -> [a]
tales que
listaAconjunto xs es el conjunto formado por los elementos de xs. Por ejemplo,λ> listaAconjunto [3, 2, 5] {2, 3, 5}
conjuntoAlista c es la lista formada por los elementos del conjunto c. Por ejemplo,λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio))) [2,3,5]
Comprobar con QuickCheck que ambas funciones son inversa; es decir,
conjuntoAlista (listaAconjunto xs) = sort (nub xs) listaAconjunto (conjuntoAlista c) = c
Un conjunto es una estructura de datos, caracterizada por ser una colección de elementos en la que no importe ni el orden ni la repetición de elementos.
Las operaciones que definen al tipo abstracto de datos (TAD) de los conjuntos (cuyos elementos son del tipo a) son las siguientes:
vacio :: Conj a inserta :: Ord a => a -> Conj a -> Conj a menor :: Ord a => Conj a -> a elimina :: Ord a => a -> Conj a -> Conj a pertenece :: Ord a => a -> Conj a -> Bool esVacio :: Conj a -> Bool
tales que
Las operaciones tienen que verificar las siguientes propiedades:
Utilizando el tipo abstracto de datos de las colas, definir las funciones
maxCola :: Ord a => Cola a -> a
tal que maxCola c sea el mayor de los elementos de la cola c. Por ejemplo,
λ> maxCola (inserta 3 (inserta 5 (inserta 1 vacia))) 5
Utilizando el tipo abstracto de datos de las colas, definir las funciones
ordenadaCola :: Ord a => Cola a -> Bool
tal que ordenadaCola c se verifica si los elementos de la cola c están ordenados en orden creciente. Por ejemplo,
ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True ordenadaCola (inserta 1 (inserta 0 (inserta 6 vacia))) == False
Utilizando el tipo abstracto de datos de las colas, definir las funciones
subCola :: Eq a => Cola a -> Cola a -> Bool
tal que subCola c1 c2 se verifica si c1 es una subcola de c2. Por ejemplo,
λ> ej1 = inserta 2 (inserta 3 vacia) λ> ej2 = inserta 7 (inserta 2 (inserta 3 (inserta 5 vacia))) λ> ej3 = inserta 2 (inserta 7 (inserta 3 (inserta 5 vacia))) λ> subCola ej1 ej2 True λ> subCola ej1 ej3 False
Utilizando el tipo abstracto de datos de las colas, definir las funciones
prefijoCola :: Eq a => Cola a -> Cola a -> Bool
tal que prefijoCola c1 c2 se verifica si la cola c1 es justamente un prefijo de la cola c2. Por ejemplo,
λ> ej1 = inserta 4 (inserta 2 vacia) λ> ej2 = inserta 5 (inserta 4 (inserta 2 vacia)) λ> ej3 = inserta 5 (inserta 2 (inserta 4 vacia)) λ> prefijoCola ej1 ej2 True λ> prefijoCola ej1 ej3 False
Utilizando el tipo abstracto de datos de las colas, definir las funciones
contenidaCola :: Eq a => Cola a -> Cola a -> Bool
tal que contenidaCola c1 c2 se verifica si todos los elementos de la cola c1 son elementos de la cola c2. Por ejemplo,
λ> ej1 = inserta 3 (inserta 2 vacia) λ> ej2 = inserta 3 (inserta 4 vacia) λ> ej3 = inserta 5 (inserta 2 (inserta 3 vacia)) λ> contenidaCola ej1 ej3 True λ> contenidaCola ej2 ej3 False
Utilizando el tipo abstracto de datos de las colas, definir las funciones
perteneceCola :: Eq a => a -> Cola a -> Bool
tal que perteneceCola x c se verifica si x es un elemento de la cola c. Por ejemplo,
perteneceCola 2 (inserta 5 (inserta 2 (inserta 3 vacia))) == True perteneceCola 4 (inserta 5 (inserta 2 (inserta 3 vacia))) == False
Utilizando el tipo abstracto de datos de las colas, definir las funciones
agrupaColas :: [Cola a] -> Cola a
tal que agrupaColas [c1,c2,c3,...,cn] es la cola formada mezclando las colas de la lista como sigue: mezcla c1 con c2, el resultado con c3, el resultado con c4, y así sucesivamente. Por ejemplo,
λ> ej1 = inserta 2 (inserta 5 vacia) λ> ej2 = inserta 3 (inserta 7 (inserta 4 vacia)) λ> ej3 = inserta 9 (inserta 0 (inserta 1 (inserta 6 vacia))) λ> agrupaColas [] - λ> agrupaColas [ej1] 5 | 2 λ> agrupaColas [ej1, ej2] 5 | 4 | 2 | 7 | 3 λ> agrupaColas [ej1, ej2, ej3] 5 | 6 | 4 | 1 | 2 | 0 | 7 | 9 | 3
Utilizando el tipo abstracto de datos de las colas, definir las funciones
intercalaColas :: Cola a -> Cola a -> Cola a
tal que intercalaColas c1 c2 es la cola formada por los elementos de c1 y c2 colocados en una cola, de forma alternativa, empezando por los elementos de c1. Por ejemplo,
λ> ej1 = inserta 3 (inserta 5 vacia) λ> ej2 = inserta 0 (inserta 7 (inserta 4 (inserta 9 vacia))) λ> intercalaColas ej1 ej2 5 | 9 | 3 | 4 | 7 | 0 λ> intercalaColas ej2 ej1 9 | 5 | 4 | 3 | 7 | 0
Utilizando el tipo abstracto de datos de las colas, definir las funciones
extiendeCola :: Cola a -> Cola a -> Cola a
tal que extiendeCola c1 c2 es la cola que resulta de poner los elementos de la cola c2 a continuación de los de la cola de c1. Por
ejemplo,
λ> ej1 = inserta 3 (inserta 2 vacia) λ> ej2 = inserta 5 (inserta 3 (inserta 4 vacia)) λ> ej1 2 | 3 λ> ej2 4 | 3 | 5 λ> extiendeCola ej1 ej2 2 | 3 | 4 | 3 | 5 λ> extiendeCola ej2 ej1 4 | 3 | 5 | 2 | 3
Utilizando el tipo abstracto de datos de las colas, definir las funciones
algunoVerifica :: (a -> Bool) -> Cola a -> Bool
tal que algunoVerifica p c se verifica si alguno de los elementos de la cola c cumplen la propiedad p. Por ejemplo,
algunoVerifica (< 0) (inserta 3 (inserta (-2) vacia)) == True algunoVerifica (< 0) (inserta 3 (inserta 2 vacia)) == False
Utilizando el tipo abstracto de datos de las colas, definir las funciones
todosVerifican :: (a -> Bool) -> Cola a -> Bool
tal que todosVerifican p c se verifica si todos los elementos de la cola c cumplen la propiedad p. Por ejemplo,
todosVerifican (>0) (inserta 3 (inserta 2 vacia)) == True todosVerifican (>0) (inserta 3 (inserta (-2) vacia)) == False
Utilizando el tipo abstracto de datos de las colas, definir las funciones
longitudCola :: Cola a -> Int
tal que longitudCola c es el número de elementos de la cola c. Por ejemplo,
longitudCola (inserta 4 (inserta 2 (inserta 5 vacia))) == 3
Utilizando el tipo abstracto de datos de las colas, definir las funciones
ultimoCola :: Cola a -> a
tal que ultimoCola c es el último elemento de la cola c. Por ejemplo,
ultimoCola (inserta 3 (inserta 5 (inserta 2 vacia))) == 3 ultimoCola (inserta 2 vacia) == 2
Utilizando el tipo abstracto de datos de las colas, definir las funciones
listaAcola :: [a] -> Cola a colaAlista :: Cola a -> [a]
tales que
listaAcola xs es la cola formada por los elementos de xs. Por ejemplo,λ> listaAcola [3, 2, 5] 3 | 2 | 5
colaAlista c es la lista formada por los elementos de la cola c. Por ejemplo,λ> colaAlista (inserta 5 (inserta 2 (inserta 3 vacia))) [3, 2, 5]
Comprobar con QuickCheck que ambas funciones son inversa; es decir,
colaAlista (listaAcola xs) = xs listaAcola (colaAlista c) = c
Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción se realiza por un extremo (el posterior o final) y la operación de extracción por el otro (el anterior o frente).
Las operaciones que definen a tipo abstracto de datos (TAD) de las colas (cuyos elementos son del tipo a) son las siguientes:
vacia :: Cola a inserta :: a -> Cola a -> Cola a primero :: Cola a -> a resto :: Cola a -> Cola a esVacia :: Cola a -> Bool
tales que
Las operaciones tienen que verificar las siguientes propiedades:
Utilizando el tipo abstracto de datos de las pilas, definir la función
maxPila :: Ord a => Pila a -> a
tal que maxPila p sea el mayor de los elementos de la pila p. Por ejemplo,
λ> maxPila (apila 3 (apila 5 (apila 1 vacia))) 5
Utilizando el tipo abstracto de datos de las pilas, definir la función
nubPila :: Eq a => Pila a -> Pila a
tal que nubPila p es la pila con los elementos de p sin repeticiones. Por ejemplo,
λ> nubPila (apila 3 (apila 1 (apila 3 (apila 5 vacia)))) 1 | 3 | 5
Utilizando el tipo abstracto de datos de las pilas, definir la función
ordenaInserPila :: Ord a => Pila a -> Pila a
tal que ordenaInserPila p es la pila obtenida ordenando por inserción los los elementos de la pila p. Por ejemplo,
λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia))) 1 | 3 | 4
Comprobar con QuickCheck que la pila (ordenaInserPila p) está ordenada.
Utilizando el tipo abstracto de datos de las pilas, definir la función
ordenadaPila :: Ord a => Pila a -> Bool
tal que ordenadaPila p se verifica si los elementos de la pila p están ordenados en orden creciente. Por ejemplo,
ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True ordenadaPila (apila 1 (apila 0 (apila 6 vacia))) == False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
subPila :: Eq a => Pila a -> Pila a -> Bool
tal que subPila p1 p2 se verifica si p1 es una subpila de p2. Por ejemplo,
λ> ej1 = apila 2 (apila 3 vacia) λ> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia))) λ> ej3 = apila 2 (apila 7 (apila 3 (apila 5 vacia))) λ> subPila ej1 ej2 True λ> subPila ej1 ej3 False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
prefijoPila :: Eq a => Pila a -> Pila a -> Bool
tal que prefijoPila p1 p2 se verifica si la pila p1 es justamente un prefijo de la pila p2. Por ejemplo,
λ> ej1 = apila 4 (apila 2 vacia) λ> ej2 = apila 4 (apila 2 (apila 5 vacia)) λ> ej3 = apila 5 (apila 4 (apila 2 vacia)) λ> prefijoPila ej1 ej2 True λ> prefijoPila ej1 ej3 False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
contenidaPila :: Eq a => Pila a -> Pila a -> Bool
tal que contenidaPila p1 p2 se verifica si todos los elementos de de la pila p1 son elementos de la pila p2. Por ejemplo,
λ> ej1 = apila 3 (apila 2 vacia) λ> ej2 = apila 3 (apila 4 vacia) λ> ej3 = apila 5 (apila 2 (apila 3 vacia)) λ> contenidaPila ej1 ej3 True λ> contenidaPila ej2 ej3 False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
pertenecePila :: Eq a => a -> Pila a -> Bool
tal que pertenecePila x p se verifica si x es un elemento de la pila p. Por ejemplo,
pertenecePila 2 (apila 5 (apila 2 (apila 3 vacia))) == True pertenecePila 4 (apila 5 (apila 2 (apila 3 vacia))) == False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
mapPila :: (a -> a) -> Pila a -> Pila a
tal que mapPila f p es la pila formada con las imágenes por f de los elementos de pila p, en el mismo orden. Por ejemplo,
λ> mapPila (+1) (apila 5 (apila 2 (apila 7 vacia))) 6 | 3 | 8
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
filtraPila :: (a -> Bool) -> Pila a -> Pila a
tal que filtraPila p q es la pila obtenida con los elementos de pila q que verifican el predicado p, en el mismo orden. Por ejemplo,
λ> ejPila = apila 6 (apila 3 (apila 1 (apila 4 vacia))) λ> ejPila 6 | 3 | 1 | 4 λ> filtraPila even ejPila 6 | 4 λ> filtraPila odd ejPila 3 | 1
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
listaApila :: [a] -> Pila a pilaALista :: Pila a -> [a]
tales que
listaApila xs es la pila formada por los elementos de xs. Por ejemplo,λ> listaApila [3, 2, 5] 5 | 2 | 3 ~~~ + `pilaALista p` es la lista formada por los elementos de la lista `p`. Por ejemplo, ~~~haskell λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia))) [3, 2, 5]
Comprobar con QuickCheck que ambas funciones son inversa; es decir,
pilaAlista (listaApila xs) == xs listaApila (pilaAlista p) == p
Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserción y extracción se realizan por el mismo extremo.
Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:
vacia :: Pila a apila :: a -> Pila a -> Pila a cima :: Pila a -> a desapila :: Pila a -> Pila a esVacia :: Pila a -> Bool
tales que
Las operaciones tienen que verificar las siguientes propiedades:
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 e. 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)
Las operaciones de suma, resta y multiplicación se pueden representar mediante el siguiente tipo de datos
data Op = S | R | M
La expresiones aritméticas con dichas operaciones se pueden representar mediante el siguiente tipo de dato algebraico
data Expr = C Int | A Op Expr Expr
Por ejemplo, la expresión
(7-3)+(2*5)
se representa por
A S (A R (C 7) (C 3)) (A M (C 2) (C 5))
Definir la función
valor :: Expr -> Int
tal que valor e es el valor de la expresión e. Por ejemplo,
valor (A S (A R (C 7) (C 3)) (A M (C 2) (C 5))) == 14 valor (A M (A R (C 7) (C 3)) (A S (C 2) (C 5))) == 28
Las expresiones aritméticas generales se pueden definir usando el siguiente tipo de datos
data Expr = C Int | X | S Expr Expr | R Expr Expr | P Expr Expr | E Expr Int deriving (Eq, Show)
Por ejemplo, la expresión
3*x - (x+2)^7
se puede definir por
R (P (C 3) X) (E (S X (C 2)) 7)
Definir la función
maximo :: Expr -> [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,
λ> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3] (100,[0,1])
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
reducible :: Expr -> 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 (S (C 3) (C 4)) == True reducible (S (C 3) (V 'x')) == False reducible (S (C 3) (P (C 4) (C 5))) == True reducible (S (V 'x') (P (C 4) (C 5))) == True reducible (S (C 3) (P (V 'x') (C 5))) == False reducible (C 3) == False reducible (V 'x') == False
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr deriving (Eq, Show)
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
sustitucion :: Expr -> [(Char, Int)] -> Expr
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,
λ> sustitucion (P (V 'z') (S (C 3) (V 'x'))) [('x',7),('z',9)] P (C 9) (S (C 3) (C 7)) λ> sustitucion (P (V 'z') (S (C 3) (V 'y'))) [('x',7),('z',9)] P (C 9) (S (C 3) (V 'y'))
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
sumas :: Expr -> Int
tal que sumas e es el número de sumas en la expresión e. Por ejemplo,
sumas (P (V 'z') (S (C 3) (V 'x'))) == 1 sumas (S (V 'z') (S (C 3) (V 'x'))) == 2 sumas (P (V 'z') (P (C 3) (V 'x'))) == 0
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
valor :: Expr -> [(Char,Int)] -> Int
tal que valor x e es el valor de la expresión x en el entorno e (es decir, el valor de la expresión donde las variables de x se sustituyen por los valores según se indican en el entorno e). Por ejemplo,
λ> valor (P (C 2) (S (V 'a') (V 'b'))) [('a',2),('b',5)] 14
La expresión 2*(a+5) puede representarse por
P (C 2) (S (V 'a') (C 5))
usando el tipo de las expresiones aritméticas con variables definido como se muestra a continuación.
module Expresion_aritmetica_con_variables where data Expr = C Int | V Char | S Expr Expr | P Expr Expr
La expresión 2*(a+5) puede representarse por
P(C(2), S(V('a'), C(5)))
usando el tipo de las expresiones aritméticas con variables definido como se muestra a continuación.
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class C(Expr): x: int @dataclass class V(Expr): x: str @dataclass class S(Expr): x: Expr y: Expr @dataclass class P(Expr): x: Expr y: Expr
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 Expr definido por
data Expr = X | C Int | S Expr Expr | P Expr Expr
Por ejemplo, la expresión X·(13+X) se representa por
P X (S (C 13) X)
Definir la función
numVars :: Expr -> Int
tal que numVars e es el número de variables en la expresión e. Por ejemplo,
numVars (C 3) == 0 numVars X == 1 numVars (P X (S (C 13) X)) == 2
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 Expr definido por
data Expr = X | C Int | S Expr Expr | P Expr Expr
Por ejemplo, la expresión X·(13+X) se representa por
P X (S (C 13) X)
Definir la función
valor :: Expr -> Int -> Int
tal que valor e n es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,
valor (P X (S (C 13) X)) 2 == 30
La expresión X·(13+X) se representa por
P(X(), S(C(13), X()))
usando el tipo de las expresiones aritméticas con una variable (denotada por X) que se define como se muestra a continuación,
data Expr = C Int | V Char | S Expr Expr | P Expr Expr
La expresión X*(13+X) se representa por
P(X(), S(C(13), X()))
usando el tipo de las expresiones aritméticas con una variable (denotada por X) que se define como se muestra a continuación,
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class X(Expr): pass @dataclass class C(Expr): x: int @dataclass class S(Expr): x: Expr y: Expr @dataclass class P(Expr): x: Expr y: Expr
Usando el tipo de las expresiones aritméticas básicas, definir la función
aplica :: (Int -> Int) -> Expr -> Expr
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,
λ> aplica (+2) (S (P (C 3) (C 5)) (P (C 6) (C 7))) S (P (C 5) (C 7)) (P (C 8) (C 9)) λ> aplica (*2) (S (P (C 3) (C 5)) (P (C 6) (C 7))) S (P (C 6) (C 10)) (P (C 12) (C 14))
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
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
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
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
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:
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)))
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)) == []
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
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
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
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
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
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
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 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,
sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21
El árbol, con valores en los nodos,
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))
usando el tipo de los árboles con valores en los nodos definido como se muestra a continuación.
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq)
El árbol binario, con valores en los nodos,
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())))
usando el tipo de los árboles binarios con valores en los nodos definido como se muestra a continuación.
from dataclasses import dataclass @dataclass class Arbol: pass @dataclass class H(Arbol): pass @dataclass class N(Arbol): x: int i: Arbol d: Arbol
El árbol binario
9 / \ / \ 3 7 / \ 2 4
se puede representar por
N 9 (N 3 (H 2) (H 4)) (H 7)
El tipo de los árboles binarios se puede definir por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq)
Definir las funciones
repeatArbol :: a -> Arbol a replicateArbol :: Int -> a -> Arbol a
tales que
repeatArbol x es es árbol con infinitos nodos x. Por ejemplo,takeArbol 0 (repeatArbol 3) == H 3 takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3) takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))
replicate n x es el árbol de profundidad n cuyos nodos son x. Por ejemplo,replicateArbol 0 5 == H 5 replicateArbol 1 5 == N 5 (H 5) (H 5) replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))
El árbol binario
9 / \ / \ 3 7 / \ 2 4
se puede representar por
N 9 (N 3 (H 2) (H 4)) (H 7)
El tipo de los árboles binarios se puede definir por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq)
La función take está definida por
take :: Int -> [a] -> [a] take 0 = [] take (n+1) [] = [] take (n+1) (x:xs) = x : take n xs
Definir la función
takeArbol :: Int -> Arbol a -> Arbol a
tal que takeArbol n t es el subárbol de t de profundidad n. Por ejemplo,
takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9 takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7) takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
Comprobar con QuickCheck que la profundidad de takeArbol n x es menor o igual que n, para todo número natural n y todo árbol x.
El árbol binario
9 / \ / \ 3 7 / \ 2 4
se puede representar por
N 9 (N 3 (H 2) (H 4)) (H 7)
El tipo de los árboles binarios se puede definir por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq)
Definir la función
espejo :: Arbol a -> Arbol a
tal que espejo x es la imagen especular del árbol x. Por ejemplo,
espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))
Comprobar con QuickCheck las siguientes propiedades, para todo árbol x,
espejo (espejo x) = x reverse (preorden (espejo x)) = postorden x postorden (espejo x) = reverse (preorden x)