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.

Leer más…

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

Leer más…

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.

Leer más…

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.

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…