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

TAD de las colas: Todos los elementos verifican una propiedad

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

tal que todosVerifican p c se verifica si todos 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

TAD de las colas: Longitud de una cola

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

tal que longitudCola c es el número de 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: Último elemento

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

tal que ultimoCola c es el último 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: Transformaciones entre colas y listas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

tales que

  • listaAcola xs es la cola formada por los elementos de xs. Por ejemplo,

  • colaAlista c es la lista formada por los elementos de la cola 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 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:

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

2. Las colas en Haskell

2.1. El tipo abstracto de datos de las colas en Haskell

El TAD de las colas se encuentra en el módulo Cola.hs cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos tres: una usando listas, otra usando pares de listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de las colas mediante listas

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

2.3. Implementación de las colas mediante pares de listas

En esta implementación, una cola c se representa mediante un par de listas (xs,ys) de modo que los elementos de c son, en ese orden, los elementos de la lista xs++(reverse ys).

Al dividir la lista en dos parte e invertir la segunda de ellas, esperamos hacer más eficiente las operaciones sobre las colas.

Impondremos también una restricción adicional sobre la representación: las colas serán representadas mediante pares (xs,ys) tales que si xs es vacía, entonces ys será también vacía. Esta restricción ha de ser conservada por los programas que crean colas.

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

2.4. Implementación de las colas mediante sucesiones

La implementación (que usa la librería Data.Sequence) se encuentra en el módulo ColaConSucesiones.hs cuyo contenido es el siguiente:

3. Las colas en Python

3.1. El tipo abstracto de las colas en Python

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

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos tres: una usando listas, otra usando pares de listas y otra usando deques. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

3.2. Implementación de las colas mediante listas

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

  • inserta(x) añade x al final de la cola.
  • primero() es el primero de la cola.
  • resto() elimina el primero de la cola.
  • 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 colas y se comprueba que las colas cumplen las propiedades de su especificación.

3.3. Implementación de las colas mediante pares de listas

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

3.4. Implementación de las colas mediante deque

La implementación (que usa la librería deque) se encuentra en el módulo colaConDeque.py y su contenido es el siguiente:

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

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

tal que maxPila p sea el mayor de los elementos de la pila 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 las pilas: Eliminación de repeticiones en una pila

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

tal que nubPila p es la pila con los elementos de p sin repeticiones. 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 pilas: Ordenación de pilas por inserción

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

tal que ordenaInserPila p es la pila obtenida ordenando por inserción los los elementos de la pila p. Por ejemplo,

Comprobar con QuickCheck que la pila (ordenaInserPila p) está ordenada.

Soluciones

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


Soluciones en Haskell


Soluciones en Python

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

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

tal que ordenadaPila p se verifica si los elementos de la pila p 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 pilas: Reconocimiento de subpilas

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

tal que subPila p1 p2 se verifica si p1 es una subpila de p2. 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 pilas: Reconocimiento de prefijos de pilas

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

tal que prefijoPila p1 p2 se verifica si la pila p1 es justamente un prefijo de la pila p2. 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 pilas: Inclusión de pilas

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

tal que contenidaPila p1 p2 se verifica si todos los elementos de de la pila p1 son elementos de la pila p2. 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 pilas: Pertenencia a una pila

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

tal que pertenecePila x p se verifica si x es un elemento de la pila 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 las pilas: Aplicación de una función a los elementos de una pila

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

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,

Soluciones

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


Soluciones en Haskell


Soluciones en Python

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

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

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,

Soluciones

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


Soluciones en Haskell


Soluciones en Python