El tipo abstracto de datos de las colas de prioridad en Haskell

PorJosé A. Alonso

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las colas de prioridad.

Una cola de prioridad (en inglés, priority queue) es una cola en la que cada elemento tiene asociada una prioridad y la operación de extracción siempre elige el elemento de menor prioridad. Un ejemplo de cola de prioridad es el formado por una lista de ciudades ordenadas por su distancia a un destino final.

El contenido del resto del artículo es el siguiente:

  • la signatura del TAD de las colas de prioridad;
  • las propiedades del TAD de las colas de prioridad;
  • la implementación, en Haskell, de las colas de prioridad mediante listas y
  • la comprobación con QuickCheck de sus propiedades.

Posteriormente, cuando se estudien los montículos, se presentará otra implementación de las colas de prioridad mediante montículos.
Read More “El tipo abstracto de datos de las colas de prioridad en Haskell”

El tipo abstracto de datos de las colas en Haskell

PorJosé A. Alonso

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las colas.

Al igual que hice en los anteriores TAD, usaré módulos, funciones de escritura y QuickCheck para conseguir la abstracción, independencia y certificación de los resultados de las implementaciones.

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 colas también se llaman estructuras FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir. Este comportamiento es análogo a las colas del cine.

El contenido del resto del artículo es el siguiente:

  • la signatura del TAD de las colas;
  • las propiedades del TAD de las colas;
  • la implementación, en Haskell, de las colas mediante listas;
  • la implementación, en Haskell, de las colas mediante pares de listas y
  • la comprobación con QuickCheck de sus propiedades.

Read More “El tipo abstracto de datos de las colas en Haskell”

El tipo abstracto de datos de las pilas en Haskell

PorJosé A. Alonso

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las pilas.

En artículos anteriores presenté los TAD de los polinomios y el de los conjuntos. En éste voy a presentar el TAD de las pilas y sus implementaciones en Haskell.

Al igual que hice en los anteriores TAD, usaré módulos, funciones de escritura y QuickCheck para conseguir la abstracción, independencia y certificación de los resultados de las implementaciones.

El contenido del resto del artículo es el siguiente: el TAD de las pilas, las implementaciones en Haskell mediante tipos algebraicos y mediante listas y la comprobación con QuickCheck de sus propiedades.
Read More “El tipo abstracto de datos de las pilas en Haskell”

El tipo abstracto de datos de los conjuntos en Haskell

PorJosé A. Alonso

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell. El objetivo de la serie es la elaboración del tema de TAD del curso de Informática del Grado en Matemáticas.

En el artículo anterior presenté el TAD de polinomios. En éste voy a presentar los TAD de conjuntos y sus implementaciones en Haskell.

Al igual que hice en el de polinomio usaré módulos, importaciones cualificadas, indefiniciones y funciones de escritura para conseguir la abstracción e independencia de los resultados de las implementaciones.

El contenido del resto del artículo es el siguiente: el TAD de los conjuntos y su implementación mediante listas no ordenadas con y sin duplicados, el TAD de los conjuntos ordenados y su implementación mediante listas ordenadas sin duplicados, el TAD de los conjuntos de números naturales y su implementación
mediante números binarios.
Read More “El tipo abstracto de datos de los conjuntos en Haskell”

El tipo abstracto de datos de los polinomios en Haskell

PorJosé A. Alonso

Como comenté en la entrada anterior, estoy elaborando los apuntes de los temas del curso Informática del Grado en Matemáticas (2010-11) no incluidos aún en el libro Temas de programación funcional (2010-11).

Uno de los temas en los que he estado trabajando últimamente es en el de los tipos abstractos de datos (TAD). Además de los habituales (pilas, colas, colas de prioridad, conjuntos, tablas, árboles binarios de búsqueda, montículos y árboles AVL), un TAD especialmente adecuado para los estudiantes de matemáticas es el de polinomios. A continuación muestro la implementación que estoy diseñando en Haskell para incluirla en el tema.

Del código deseo resaltar las siguientes características:

  • Independización de los resultados de las implementaciones mediante las funciones de escritura.
  • Comprobación de las implementaciones con QuickCheck mediante las funciones generadoras de polinomios.

A continuación muestro los ficheros con los códigos desarrollados.
Read More “El tipo abstracto de datos de los polinomios en Haskell”