Un enfoque ecléctico para la implementación de estructuras de datos

Abstract

Este trabajo de grado pone énfasis en el estudio de las estructuras de datos desde el punto de vista del paradigma de programación funcional. Bajo el paradigma funcional, las estructuras de datos pueden clasificarse de dos maneras, según su implementación se base o no en efectos laterales. Las estructuras de datos que no basan su implementación en efectos laterales se denominan funcionales puras; un ejemplo clásico son los árboles o colas de prioridad. Aquellas que necesitan recurrir a los efectos laterales con el fin de obtener una implementación eficiente se conocen como estructuras de datos procedurales o imperativas (p. ej., tablas hash). Esta tesis persigue los siguientes objetivos: - Implementar dentro del paradigma funcional estructuras de datos tanto funcionales puras como imperativas que no sean trivilaes y que además utilicen adecuadamente las ventajas que brinda dicho paradigma. Las implementaciones funcionales puras deben ser simples, de modo que sea sencillo razonar sobre su correctitud. Las procedurales deben estar implementadas de modo tal que no sea una mera copia de sus contrapartes imperativas, sino que utilicen las ventajas ofrecidas por el paradigma, comúnmente asociadas a los programas funcionales puros. - Explorar distintas alternativas de implementación. Se verá que distintos lenguajes funcionales presentan diferentes características que impactan sobre las técnicas de implementación de estructuras de datos. Este trabajo intenta analizar las ventajas y desventajas que ellas presentan. - Obtener implementaciones eficientes, o sea, con tiempos de ejecución comparables a los obtenidos por una implementación imperativa. Para esto es importante disponer de versiones imperativas con el fin de tener un patrón contra el cual comparar el rendimiento de las implementaciones funcionales.