Representación de estructuras de datos con invariantes en Haskell

Abstract

Las estructuras de datos utilizadas en programación se caracterizan por mantener un conjunto de invariantes. Dependiendo del lenguaje y paradigma de programación utilizados, estos invariantes son verificados en tiempo de ejecución o compilación. En este proyecto de grado se presenta el problema de implementar invariantes de distintas estructuras de datos en el lenguaje Haskell, utilizando las herramientas que el lenguaje provee para programar a nivel de tipos. La verificación de estos invariantes se realiza en tiempo de compilación. Se implementan árboles binarios de búsqueda (BST) y árboles balanceados (AVL). Ambos son implementados siguiendo tres enfoques diferentes, dependiendo de la forma en que se implementan los invariantes. Se realiza una comparación de estos enfoques desde distintos ángulos: desempeño, modularidad del código, etc.