El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Término independiente de un polinomio

José A. Alonso

15-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Método de Horner del valor de un polinomio

José A. Alonso

12-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Divisibilidad de polinomios

José A. Alonso

11-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - División de polinomios

José A. Alonso

10-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Multiplicación de un polinomio por un número

José A. Alonso

09-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Integral definida de un polinomio

José A. Alonso

08-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Integral de un polinomio

José A. Alonso

05-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Potencia de un polinomio

José A. Alonso

04-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Resta de polinomios

José A. Alonso

03-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Derivada de un polinomio

José A. Alonso

02-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Comprobación de raíces de polinomios

José A. Alonso

01-05-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Valor de un polinomio en un punto

José A. Alonso

28-04-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Producto de polinomios

José A. Alonso

27-04-2023

El tipo abstracto de datos de los polinomios

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

El producto de polinomios es conmutativo.
El producto es distributivo respecto de la suma.

TAD de los polinomios - Suma de polinomios

José A. Alonso

26-04-2023

El tipo abstracto de datos de los polinomios

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.
la suma es conmutativa.

TAD de los polinomios - Término líder de un polinomio

José A. Alonso

25-04-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Construcción de términos

José A. Alonso

24-04-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Transformaciones entre polinomios y listas densas

José A. Alonso

21-04-2023

El tipo abstracto de datos de los polinomios

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.

TAD de los polinomios - Coeficiente del término de grado k

José A. Alonso

20-04-2023

El tipo abstracto de datos de los polinomios

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

TAD de los polinomios - Transformaciones entre polinomios y listas dispersas

José A. Alonso

19-04-2023

El tipo abstracto de datos de los polinomios

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.

TAD de los polinomios - Transformaciones entre las representaciones dispersa y densa

José A. Alonso

18-04-2023

El tipo abstracto de datos de los polinomios

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.

El tipo abstracto de datos de los polinomios

José A. Alonso

17-04-2023

El tipo abstracto de datos de los polinomios

1. El tipo abstracto de datos de los polinomios

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

polCero es el polinomio cero.
(esPolCero p) se verifica si p es el polinomio cero.
(consPol n b p) es el polinomio bx^n+p
(grado p) es el grado del polinomio p.
(coefLider p) es el coeficiente líder del polinomio p.
(restoPol p) es el resto del polinomio p.

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:

esPolCero polCero
n > grado p && b /= 0 ==> not (esPolCero (consPol n b p))
consPol (grado p) (coefLider p) (restoPol p) == p
n > grado p && b /= 0 ==> grado (consPol n b p) == n
n > grado p && b /= 0 ==> coefLider (consPol n b p) == b
n > grado p && b /= 0 ==> restoPol (consPol n b p) == p

Clausura transitiva

José A. Alonso

14-04-2023

Relaciones binarias

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.

Clausura simétrica

José A. Alonso

13-04-2023

Relaciones binarias

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.

Clausura reflexiva

José A. Alonso

12-04-2023

Relaciones binarias

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)])

Relaciones totales

José A. Alonso

11-04-2023

Relaciones binarias

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

Relaciones antisimétricas

José A. Alonso

10-04-2023

Relaciones binarias

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

Relaciones irreflexivas

José A. Alonso

09-04-2023

Relaciones binarias

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

Relaciones de equivalencia

José A. Alonso

06-04-2023

Relaciones binarias

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

Relaciones transitivas

José A. Alonso

05-04-2023

Relaciones binarias

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

Reconocimiento de subconjunto

José A. Alonso

04-04-2023

Relaciones binarias

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

Relaciones simétricas

José A. Alonso

03-04-2023

Relaciones binarias

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)])

Relaciones simétricas

José A. Alonso

31-03-2023

Relaciones binarias

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

Relaciones reflexivas

José A. Alonso

30-03-2023

Relaciones binarias

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

Universo y grafo de una relación binaria

José A. Alonso

29-03-2023

Relaciones binarias

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)]

Relaciones binarias

José A. Alonso

28-03-2023

Relaciones binarias

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.

TAD de los conjuntos - TAD Producto cartesiano

José A. Alonso

27-03-2023

El tipo abstracto de datos de los conjuntos

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)}

TAD de los conjuntos - Algunos elementos verifican una propiedad

José A. Alonso

24-03-2023

El tipo abstracto de datos de los conjuntos

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

TAD de los conjuntos - Todos los elementos verifican una propiedad

José A. Alonso

23-03-2023

El tipo abstracto de datos de los conjuntos

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

TAD de los conjuntos - Aplicación de una función a los elementos de un conjunto

José A. Alonso

22-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjuntos - Partición según un número

José A. Alonso

21-03-2023

El tipo abstracto de datos de los conjuntos

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})

TAD de los conjuntos - Partición de un conjunto según una propiedad

José A. Alonso

20-03-2023

El tipo abstracto de datos de los conjuntos

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})

TAD de los conjuntos - Subconjunto determinado por una propiedad

José A. Alonso

17-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjuntos - Diferencia simétrica

José A. Alonso

16-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjuntos - Diferencia de conjuntos

José A. Alonso

15-03-2023

El tipo abstracto de datos de los conjuntos

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
   {}

TAD de los conjuntos - Conjuntos disjuntos

José A. Alonso

14-03-2023

El tipo abstracto de datos de los conjuntos

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

TAD de los conjuntos - Intersección de varios conjuntos

José A. Alonso

13-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjuntos - Intersección de dos conjuntos

José A. Alonso

10-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjunto - Unión de varios conjuntos

José A. Alonso

09-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjuntos - Unión de dos conjuntos

José A. Alonso

08-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjuntos - Número de elementos de un conjunto

José A. Alonso

07-03-2023

El tipo abstracto de datos de los conjuntos

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

TAD de los conjuntos - Conjunto unitario

José A. Alonso

06-03-2023

El tipo abstracto de datos de los conjuntos

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}

TAD de los conjuntos - Reconocimiento de subconjunto propio

José A. Alonso

03-03-2023

El tipo abstracto de datos de los conjuntos

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

TAD de los conjuntos - Reconocimiento de subconjunto

José A. Alonso

02-03-2023

El tipo abstracto de datos de los conjuntos

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

TAD de los conjuntos - Transformaciones entre conjuntos y listas

José A. Alonso

01-03-2023

El tipo abstracto de datos de los conjuntos

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

El tipo abstracto de datos de los conjuntos

José A. Alonso

28-02-2023

El tipo abstracto de datos de los conjuntos

1. El tipo abstracto de datos de los conjuntos

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

vacio es el conjunto vacío.
(inserta x c) es el conjunto obtenido añadiendo el elemento x al conjunto c.
(menor c) es el menor elemento del conjunto c.
(elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c.
(pertenece x c) se verifica si x pertenece al conjunto c.
(esVacio c) se verifica si c es el conjunto vacío.

Las operaciones tienen que verificar las siguientes propiedades:

inserta x (inserta x c) == inserta x c
inserta x (inserta y c) == inserta y (inserta x c)
not (pertenece x vacio)
pertenece y (inserta x c) == (x==y) || pertenece y c
elimina x vacio == vacio
Si x == y, entonces elimina x (inserta y c) == elimina x c
Si x /= y, entonces elimina x (inserta y c) == inserta y (elimina x c)
esVacio vacio
not (esVacio (inserta x c))

TAD de las colas - Máximo elemento de una cola

José A. Alonso

27-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Reconocimiento de ordenación de colas

José A. Alonso

24-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Reconocimiento de subcolas

José A. Alonso

23-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Reconocimiento de prefijos de colas

José A. Alonso

22-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Inclusión de colas

José A. Alonso

21-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Pertenencia a una cola

José A. Alonso

20-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Agrupación de colas

José A. Alonso

17-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Intercalado de dos colas

José A. Alonso

16-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Extensión de colas

José A. Alonso

15-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Alguno de los elementos verifican una propiedad

José A. Alonso

14-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Todos los elementos verifican una propiedad

José A. Alonso

13-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Longitud de una cola

José A. Alonso

10-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Último elemento

José A. Alonso

09-02-2023

El tipo abstracto de datos de las colas

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

TAD de las colas - Transformaciones entre colas y listas

José A. Alonso

08-02-2023

El tipo abstracto de datos de las colas

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

El tipo abstracto de datos de las colas

José A. Alonso

07-02-2023

El tipo abstracto de datos de las colas

1. El tipo abstracto de datos de las colas

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

vacia es la cola vacía.
(inserta x c) es la cola obtenida añadiendo x al final de c.
(primero c) es el primero de la cola c.
(resto c) es la cola obtenida eliminando el primero de c.
(esVacia c) se verifica si c es la cola vacía.

Las operaciones tienen que verificar las siguientes propiedades:

primero (inserta x vacia) == x
Si c es una cola no vacía, entonces primero (inserta x c) == primero c,
resto (inserta x vacia) == vacia
Si c es una cola no vacía, entonces resto (inserta x c) == inserta x (resto c)
esVacia vacia
not (esVacia (inserta x c))

TAD de las pilas - Máximo elemento de una pila

José A. Alonso

06-02-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Eliminación de repeticiones en una pila

José A. Alonso

03-02-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Ordenación de pilas por inserción

José A. Alonso

02-02-2023

El tipo abstracto de datos de las pilas

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.

TAD de las pilas - Reconocimiento de ordenación de pilas

José A. Alonso

01-02-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Reconocimiento de subpilas

José A. Alonso

31-01-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Reconocimiento de prefijos de pilas

José A. Alonso

28-01-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Inclusión de pilas

José A. Alonso

27-01-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Pertenencia a una pila

José A. Alonso

26-01-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Aplicación de una función a los elementos de una pila

José A. Alonso

25-01-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Filtrado de pilas según una propiedad

José A. Alonso

24-01-2023

El tipo abstracto de datos de las pilas

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

TAD de las pilas - Transformaciones entre pilas y listas

José A. Alonso

23-01-2023

El tipo abstracto de datos de las pilas

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

El tipo abstracto de datos de las pilas

José A. Alonso

20-01-2023

El tipo abstracto de datos de las pilas

1. El tipo abstracto de datos de las pilas

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

vacia es la pila vacía.
(apila x p) es la pila obtenida añadiendo x al principio de p.
(cima p) es la cima de la pila p.
(desapila p) es la pila obtenida suprimiendo la cima de p.
(esVacia p) se verifica si p es la pila vacía.

Las operaciones tienen que verificar las siguientes propiedades:

cima(apila(x, p) == x
desapila(apila(x, p)) == p
esVacia(vacia)
not esVacia(apila(x, p))

Valor de una expresión vectorial

José A. Alonso

19-01-2023

Tipos definidos y tipos de datos algebraicos

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)

Valor de expresiones aritméticas generales

José A. Alonso

18-01-2023

Tipos definidos y tipos de datos algebraicos

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

Máximos valores de una expresión aritmética

José A. Alonso

17-01-2023

Tipos definidos y tipos de datos algebraicos

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])

Expresiones aritméticas reducibles

José A. Alonso

16-01-2023

Tipos definidos y tipos de datos algebraicos

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

Sustitución en una expresión aritmética

José A. Alonso

13-01-2023

Tipos definidos y tipos de datos algebraicos

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'))

Número de sumas en una expresión aritmética

José A. Alonso

12-01-2023

Tipos definidos y tipos de datos algebraicos

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

Valor de una expresión aritmética con variables

José A. Alonso

11-01-2023

Tipos definidos y tipos de datos algebraicos

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

El tipo de las expresiones aritméticas con variables

José A. Alonso

11-01-2023

Tipos definidos y tipos de datos algebraicos

1. El tipo de las expresiones aritméticas con variables en Haskell

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

2. El tipo de las expresiones aritméticas con variables en Python

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

Número de variables de una expresión aritmética

José A. Alonso

10-01-2023

Tipos definidos y tipos de datos algebraicos

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

Valor de una expresión aritmética con una variable

José A. Alonso

09-01-2023

Tipos definidos y tipos de datos algebraicos

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

Tipo de expresiones aritméticas con una variable

José A. Alonso

09-01-2023

Tipos definidos y tipos de datos algebraicos

1. El tipo de las expresiones aritméticas con una variable en Haskell

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

2. El tipo de las expresiones aritméticas con una variable en Python

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

Aplicación de una función a una expresión aritmética

José A. Alonso

06-01-2023

Tipos definidos y tipos de datos algebraicos

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))

Valor de una expresión aritmética básica

José A. Alonso

05-01-2023

Tipos definidos y tipos de datos algebraicos

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

José A. Alonso

05-01-2023

Tipos definidos y tipos de datos algebraicos

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

José A. Alonso

04-01-2023

Tipos definidos y tipos de datos algebraicos

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

José A. Alonso

03-01-2023

Tipos definidos y tipos de datos algebraicos

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

José A. Alonso

02-01-2023

Tipos definidos y tipos de datos algebraicos

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

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))  ==  []