I1M2018: El TAD de los montículos en Haskell

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de datos de los montículos en Haskell.

En primer lugar, se han introduccido los montículos usando el artículo Functional heap – Leftist tree.

En segundo lugar, se ha seguido el mismo patrón que en los anteriores tipos de datos para estudiar el TAD de los montículos:

  • elección de las operaciones básicas,
  • especificación de sus propiedades,
  • implementación en Haskel,
  • análisis de la complejidad de las definiciones de las operaciones básicas y
  • verificación con QuickCheck de sus propiedades características.

En tercer lugar, se ha usado los montículos para implementar el TAD de las colas de prioridad.

Finalmente, se ha comentado las librerías de Haskell para montículos: Data.Heap.Leftist y Data.Heap. La primera se corresponde totalmente con la implementación presentada en clase y la segunda es una generalización ampliada.

Los apuntes correspondientes a la clase son