Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbutrary.
Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los vértices de g son iguales.
El grado positivo de un vértice v de un grafo g es el número de vértices de g adyacentes con v y su grado negativo es el número de vértices de g incidentes con v.
Usando el tipo abstrado de datos de los grafos, definir las funciones
gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int
tales que
+ gradoPos g v es el grado positivo del vértice v en el grafo g. Por ejemplo,
λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] λ> g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] λ> gradoPos g1 5 4 λ> gradoPos g2 5 0 λ> gradoPos g2 1 3
gradoNeg g v es el grado negativo del vértice v en el grafo g. Por ejemplo,λ> gradoNeg g1 5 4 λ> gradoNeg g2 5 3 λ> gradoNeg g2 1 0
Usando el tipo abstrado de datos de los grafos, definir la función
nAristas :: (Ix v,Num p) => Grafo v p -> Int
tal que nAristas g es el número de aristas del grafo g. Si g es no dirigido, las aristas de v1 a v2 y de v2 a v1 sólo se cuentan una vez. Por ejemplo,
λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] λ> g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] λ> g3 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] λ> g4 = creaGrafo' ND (1,4) [(1,1),(1,2),(3,3)] λ> nAristas g1 8 λ> nAristas g2 7 λ> nAristas g3 4 λ> nAristas g4 3 λ> nAristas (completo 4) 6 λ> nAristas (completo 5) 10
Definir la función
prop_nAristasCompleto :: Int -> Bool
tal que prop_nAristasCompleto n se verifica si el número de aristas del grafo completo de orden n es n*(n-1)/2 y, usando la función, comprobar que la propiedad se cumple para n de 1 a 20.
Usando el tipo abstrado de datos de los grafos, definir las funciones
lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)] nLazos :: (Ix v,Num p) => Grafo v p -> Int
tales que
lazos g es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafo g. Por ejemplo,λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)] λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)] λ> lazos ej1 [(1,1),(3,3)] λ> lazos ej2 []
nLazos g es el número de lazos del grafo g. Por ejemplo,λ> nLazos ej1 2 λ> nLazos ej2 0
En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.
Usando el tipo abstrado de datos de los grafos, definir la función,
contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]
tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,
λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g1 1 [2,3] λ> contiguos g1 2 [2,1,3] λ> contiguos g1 3 [1,2] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g2 1 [2,3] λ> contiguos g2 2 [1,2,3] λ> contiguos g2 3 [1,2]
En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.
Usando el tipo abstrado de datos de los grafos, definir la función,
incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
tal que incidentes g v es la lista de los vértices incidentes en el vértice v. Por ejemplo,
λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> incidentes g1 1 [3] λ> incidentes g1 2 [1,2,3] λ> incidentes g1 3 [] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> incidentes g2 1 [2,3] λ> incidentes g2 2 [1,2,3] λ> incidentes g2 3 [1,2]
Usando el tipo abstrado de datos de los grafos, definir la función,
nVertices :: (Ix v, Num p) => Grafo v p -> Int
tal que nVertices g es el número de vértices del grafo g. Por
ejemplo,
nVertices (creaGrafo' D (1,5) [(1,2),(3,1)]) == 5 nVertices (creaGrafo' ND (2,4) [(1,2),(3,1)]) == 3
El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,...,n} y las aristas son
(1,2), (2,3), ..., (n-1,n), (n,1)
Usando el tipo abstrado de datos de los grafos, definir la función,
grafoCiclo :: Int -> Grafo Int Int
tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,
λ> grafoCiclo 3 G ND ([1,2,3],[(1,2),(1,3),(2,3)])
El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.
Usando el tipo abstrado de datos de los grafos, definir la función,
completo :: Int -> Grafo Int Int
tal que completo n es el grafo completo de orden n. Por ejemplo,
λ> completo 4 G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])
Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.
Por ejemplo,
12 1 -------- 2 | \78 /| | \ 32/ | | \ / | 34| 5 |55 | / \ | | /44 \ | | / 93\| 3 -------- 4 61
representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.
El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.
En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:
Las operaciones del tipo abstracto de datos (TAD) de los grafos son
creaGrafo :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] nodos :: (Ix v,Num p) => (Grafo v p) -> [v] aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)] aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.
Usando el TAD de los grafos, el grafo anterior se puede definir por
creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)]
con los siguientes argumentos:
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes: + mediante lista de adyacencia, + mediante vector de adyacencia y + mediante matriz de adyacencia.
Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.
Utilizando el tipo abstracto de datos de los polinomios definir la función
factorizacion :: Polinomio Int -> [Polinomio Int]
tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,
λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol1 x^5 + 5*x^2 + 4*x λ> factorizacion ejPol1 [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4] λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol2 x^3 + 2*x^2 + -1*x + -2 λ> factorizacion ejPol2 [1*x + -1,1*x + 1,1*x + 2,1]
Utilizando el tipo abstracto de datos de los polinomios definir la función
raicesRuffini :: Polinomio Int -> [Int]
tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,
λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) λ> ejPol1 3*x^4 + -5*x^2 + 3 λ> raicesRuffini ejPol1 [] λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol2 x^5 + 5*x^2 + 4*x λ> raicesRuffini ejPol2 [0,-1] λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero) λ> ejPol3 6*x^4 + 2*x λ> raicesRuffini ejPol3 [0] λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol4 x^3 + 2*x^2 + -1*x + -2 λ> raicesRuffini ejPol4 [1,-1,-2]
Utilizando el tipo abstracto de datos de los polinomios definir la función
esRaizRuffini :: Int -> Polinomio Int -> Bool
tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,
λ> ejPol = consPol 4 6 (consPol 1 2 polCero) λ> ejPol 6*x^4 + 2*x λ> esRaizRuffini 0 ejPol True λ> esRaizRuffini 1 ejPol False
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int restoRuffini :: Int -> Polinomio Int -> Int
tales que
cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol x^3 + 2*x^2 + -1*x + -2 λ> cocienteRuffini 2 ejPol x^2 + 4*x + 7 λ> cocienteRuffini (-2) ejPol x^2 + -1 λ> cocienteRuffini 3 ejPol x^2 + 5*x + 14
restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,λ> restoRuffini 2 ejPol 12 λ> restoRuffini (-2) ejPol 0 λ> restoRuffini 3 ejPol 40
Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.
Utilizando el tipo abstracto de datos de los polinomios definir la función
ruffiniDensa :: Int -> [Int] -> [Int]
tal que ruffiniDensa r cs es la lista de los coeficientes del cociente junto con el rsto que resulta de aplicar la regla de Ruffini para dividir el polinomio cuya representación densa es cs entre x-r. Por ejemplo,
ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12] ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0]
ya que
| 1 2 -1 -2 | 1 2 -1 -2 2 | 2 8 14 1 | 1 3 2 --+-------------- --+------------- | 1 4 7 12 | 1 3 2 0
Utilizando el tipo abstracto de datos de los polinomios definir la función
terminoIndep :: (Num a, Eq a) => Polinomio a -> a
tal que terminoIndep p es el término independiente del polinomio p. Por ejemplo,
λ> ejPol1 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero)) λ> ejPol1 3*x^4 + 5*x^2 + 3 λ> terminoIndep ejPol1 3 λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol2 x^5 + 5*x^2 + 4*x λ> terminoIndep ejPol2 0
El método de Horner para calcular el valor de un polinomio se basa en representarlo de una forma forma alernativa. Por ejemplo, para calcular el valor de
a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f
se representa como
(((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f
y se evalúa de dentro hacia afuera; es decir,
v(0) = 0 v(1) = v(0)*x+a = 0*x+a = a v(2) = v(1)*x+b = a*x+b v(3) = v(2)*x+c = (a*x+b)*x+c = a*x^2+b*x+c v(4) = v(3)*x+d = (a*x^2+b*x+c)*x+d = a*x^3+b*x^2+c*x+d v(5) = v(4)*x+e = (a*x^3+b*x^2+c*x+d)*x+e = a*x^4+b*x^3+c*x^2+d*x+e v(6) = v(5)*x+f = (a*x^4+b*x^3+c*x^2+d*x+e)*x+f = a*x^5+b*x^4+c*x^3+d*x^2+e*x+f
Utilizando el tipo abstracto de datos de los polinomios definir la función
horner :: (Num a, Eq a) => Polinomio a -> a -> a
tal que horner p x es el valor del polinomio p al sustituir su variable por el número x. Por ejemplo,
λ> pol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> pol1 x^5 + 5*x^2 + 4*x λ> horner pol1 0 0 λ> horner pol1 1 10 λ> horner pol1 1.5 24.84375 λ> import Data.Ratio λ> horner pol1 (3%2) 795 % 32
Utilizando el tipo abstracto de datos de los polinomios definir la función
divisiblePol :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Bool
tal que divisiblePol p q se verifica si el polinomio p es divisible por el polinomio q. Por ejemplo,
λ> pol1 = consPol 2 8 (consPol 1 14 (consPol 0 3 polCero)) λ> pol1 8*x^2 + 14*x + 3 λ> pol2 = consPol 1 2 (consPol 0 3 polCero) λ> pol2 2*x + 3 λ> pol3 = consPol 2 6 (consPol 1 2 polCero) λ> pol3 6*x^2 + 2*x λ> divisiblePol pol1 pol2 True λ> divisiblePol pol1 pol3 False
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
cociente :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a resto :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
tales que
cociente p q es el cociente de la división de p entre q. Por ejemplo,λ> pol1 = consPol 3 2 (consPol 2 9 (consPol 1 10 (consPol 0 4 polCero))) λ> pol1 2*x^3 + 9*x^2 + 10*x + 4 λ> pol2 = consPol 2 1 (consPol 1 3 polCero) λ> pol2 x^2 + 3*x λ> cociente pol1 pol2 2.0*x + 3.0
resto p q es el resto de la división de p entre q. Por ejemplo,λ> resto pol1 pol2 1.0*x + 4.0
Utilizando el tipo abstracto de datos de los polinomios definir la función
multEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a
tal que multEscalar c p es el polinomio obtenido multiplicando el número c por el polinomio p. Por ejemplo,
λ> ejPol = consPol 1 2 (consPol 0 3 polCero) λ> ejPol 2*x + 3 λ> multEscalar 4 ejPol 8*x + 12 λ> multEscalar (1 % 4) ejPol 1 % 2*x + 3 % 4
Utilizando el tipo abstracto de datos de los polinomios definir la función
integralDef :: (Fractional t, Eq t) => Polinomio t -> t -> t -> t
tal que integralDef p a b es la integral definida del polinomio p entre a y b. Por ejemplo,
λ> ejPol = consPol 7 2 (consPol 4 5 (consPol 2 5 polCero)) λ> ejPol 2*x^7 + 5*x^4 + 5*x^2 λ> integralDef ejPol 0 1 2.916666666666667 λ> integralDef ejPol 0 1 :: Rational 35 % 12
Utilizando el tipo abstracto de datos de los polinomios definir la función
integral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a
tal que integral p es la integral del polinomio p cuyos coefientes son números racionales. Por ejemplo,
λ> ejPol = consPol 7 2 (consPol 4 5 (consPol 2 5 polCero)) λ> ejPol 2*x^7 + 5*x^4 + 5*x^2 λ> integral ejPol 0.25*x^8 + x^5 + 1.6666666666666667*x^3 λ> integral ejPol :: Polinomio Rational 1 % 4*x^8 + x^5 + 5 % 3*x^3
Utilizando el tipo abstracto de datos de los polinomios definir la función
potencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
tal que potencia p n es la potencia n-ésima del polinomio p. Por ejemplo,
λ> ejPol = consPol 1 2 (consPol 0 3 polCero) λ> ejPol 2*x + 3 λ> potencia ejPol 2 4*x^2 + 12*x + 9 λ> potencia ejPol 3 8*x^3 + 36*x^2 + 54*x + 27
Utilizando el tipo abstracto de datos de los polinomios definir la función
restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
tal que restaPol p q es el polinomio obtenido restándole a p el q. Por ejemplo,
λ> ejPol1 = consPol 5 1 (consPol 4 5 (consPol 2 5 (consPol 0 9 polCero))) λ> ejPol2 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero)) λ> ejPol1 x^5 + 5*x^4 + 5*x^2 + 9 λ> ejPol2 3*x^4 + 5*x^2 + 3 λ> restaPol ejPol1 ejPol2 x^5 + 2*x^4 + 6
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])