TAD de los conjuntos: Producto cartesiano de dos conjuntos

Utilizando el tipo abstracto de datos de los conjuntos (https://bit.ly/3HbB7fo) definir la función

tal que productoC c1 c2 es el producto cartesiano de los conjuntos c1 y c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Algunos elementos verifican una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que algunos p c se verifica si algún elemento de c verifica el predicado p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Todos los elementos verifican una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que todos p c se verifica si todos los elemsntos de c verifican el predicado p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

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

Utilizando el tipo abstracto de datos de los conjuntos definir la función

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,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

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

Utilizando el tipo abstracto de datos de los conjuntos definir la función

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,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

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

Utilizando el tipo abstracto de datos de los conjuntos definir la función

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,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Subconjunto determinado por una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal filtra p c es el conjunto de elementos de c que verifican el predicado p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Diferencia simétrica

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que diferenciaSimetrica c1 c2 es la diferencia simétrica de los conjuntos c1 y c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Diferencia de conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que diferencia c1 c2 es el conjunto de los elementos de c1 que no son elementos de c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Conjuntos disjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que disjuntos c1 c2 se verifica si los conjuntos c1 y c2 son disjuntos. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Intersección de varios conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que interseccionG cs es la intersección de la lista de conjuntos cs. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Intersección de dos conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que interseccion c1 c2 es la intersección de los conjuntos c1 y c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Unión de varios conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal unionG cs calcule la unión de la lista de conjuntos cs. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Unión de dos conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal union c1 c2 es la unión de ambos conjuntos. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

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

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que cardinal c es el número de elementos del conjunto c. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Conjunto unitario

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que unitario x es el conjunto {x}. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Reconocimiento de subconjunto propio

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal subconjuntoPropio c1 c2 se verifica si c1 es un subconjunto propio de c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Reconocimiento de subconjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que subconjunto c1 c2 se verifica si todos los elementos de c1 pertenecen a c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Transformaciones entre conjuntos y listas

Utilizando el tipo abstracto de datos de los conjuntos definir las funciones

tales que
+ listaAconjunto xs es el conjunto formado por los elementos de xs. Por ejemplo,

  • conjuntoAlista c es la lista formada por los elementos del conjunto c. Por ejemplo,

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

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:

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

2. Los conjuntos en Haskell

2.1. El tipo abstracto de datos de los conjuntos en Haskell

El TAD de los conjuntos se encuentra en el módulo Conjunto.hs cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

  • mediante listas no ordenadas con duplicados,
  • mediante listas no ordenadas sin duplicados,
  • mediante listas ordenadas sin duplicados y
  • mediante la librería de conjuntos.

2.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

La implementación se encuentra en el módulo ConjuntoConListasNoOrdenadasConDuplicados.hs cuyo contenido es el siguiente:

2.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

La implementación se encuentra en el módulo ConjuntoConListasNoOrdenadasSinDuplicados.hs cuyo contenido es el siguiente:

2.4. Implementación de los conjuntos mediante listas ordenadas sin repeticiones

La implementación se encuentra en el módulo ConjuntoConListasOrdenadasSinDuplicados.hs cuyo contenido es el siguiente:

2.5. Implementación de los conjuntos mediante librería

La implementación se encuentra en el módulo ConjuntoConLibreria.hs cuyo contenido es el siguiente:

3. Los conjuntos en Python

3.1. El tipo abstracto de los conjuntos en Python

La implementación se encuentra en el módulo conjunto.py cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

  • mediante listas no ordenadas con duplicados,
  • mediante listas no ordenadas sin duplicados,
  • mediante listas ordenadas sin duplicados y
  • mediante la librería de conjuntos.

3.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

La implementación se encuentra en el módulo conjuntoConListasNoOrdenadasConDuplicados.py en el que se define la clase Conj con los siguientes métodos:

  • inserta(x) añade x al conjunto.
  • menor() es el menor elemento del conjunto.
  • elimina(x) elimina las ocurrencias de x en el conjunto.
  • pertenece(x) se verifica si x pertenece al conjunto.
  • esVacia() se verifica si la cola es vacía.

Por ejemplo,

Además se definen las correspondientes funciones. Por ejemplo,

Finalmente, se define un generador aleatorio de conjuntos y se comprueba que los conjuntos cumplen las propiedades de su especificación.

3.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

La implementación se encuentra en el módulo conjuntoConListasNoOrdenadasSinDuplicados.py cuyo contenido es

3.4. Implementación de los conjuntos mediante listas ordenadas sin duplicados

La implementación se encuentra en el módulo conjuntoConListasOrdenadasSinDuplicados.py cuyo contenido es el siguiente:

3.5. Implementación de los conjuntos mediante librería

La implementación se encuentra en el módulo conjuntoConLibreria.py cuyo contenido es el siguiente:

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

Utilizando el tipo abstracto de datos de las colas, definir la función

tal que maxCola c sea el mayor de los elementos de la cola c. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

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

Utilizando el tipo abstracto de datos de las colas, definir la función

tal que ordenadaCola c se verifica si los elementos de la cola c están ordenados en orden creciente. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las colas: Reconocimiento de subcolas

Utilizando el tipo abstracto de datos de las colas, definir la función

tal que subCola c1 c2 se verifica si c1 es una subcola de c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las colas: Reconocimiento de prefijos de colas

Utilizando el tipo abstracto de datos de las colas, definir la función

tal que prefijoCola c1 c2 se verifica si la cola c1 es justamente un prefijo de la cola c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las colas: Inclusión de colas

Utilizando el tipo abstracto de datos de las colas, definir la función

tal que contenidaCola c1 c2 se verifica si todos los elementos de la cola c1 son elementos de la cola c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las colas: Pertenencia a una cola

Utilizando el tipo abstracto de datos de las colas, definir la función

tal que perteneceCola x c se verifica si x es un elemento de la cola c. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las colas: Agrupación de colas

Utilizando el tipo abstracto de datos de las colas, definir la función

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,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las colas: Intercalado de dos colas

Utilizando el tipo abstracto de datos de las colas, definir la función

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,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las colas: Extensión de colas

Utilizando el tipo abstracto de datos de las colas, definir la función

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,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

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

Utilizando el tipo abstracto de datos de las colas, definir la función

tal que algunoVerifica p c se verifica si alguno de los elementos de la cola c cumplen la propiedad p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python