En informática , una estructura de datos puramente funcional es una estructura de datos que se puede implementar en un lenguaje puramente funcional . La principal diferencia entre una estructura de datos arbitraria y una puramente funcional es que esta última es (fuertemente) inmutable . Esta restricción garantiza que la estructura de datos posea las ventajas de los objetos inmutables: persistencia (completa) , copia rápida de objetos y seguridad de subprocesos . Las estructuras de datos eficientes puramente funcionales pueden requerir el uso de evaluación y memorización perezosas .
Definición
Las estructuras de datos persistentes tienen la propiedad de mantener sin modificar versiones anteriores de sí mismas. Por otro lado, estructuras como las matrices admiten una actualización destructiva , [1] es decir, una actualización que no se puede revertir. Una vez que un programa escribe un valor en algún índice de la matriz, su valor anterior ya no se puede recuperar. [ cita requerida ]
Formalmente, una estructura de datos puramente funcional es una estructura de datos que se puede implementar en un lenguaje puramente funcional , como Haskell . En la práctica, significa que las estructuras de datos deben construirse utilizando solo estructuras de datos persistentes como tuplas, tipos de suma , tipos de productos y tipos básicos como números enteros, caracteres, cadenas. Tal estructura de datos es necesariamente persistente. Sin embargo, todas las estructuras de datos persistentes no son puramente funcionales. [1] : 16 Por ejemplo, una matriz persistente es una estructura de datos que es persistente y que se implementa mediante una matriz, por lo que no es puramente funcional. [ cita requerida ]
En el libro Estructuras de datos puramente funcionales , Okasaki compara las actualizaciones destructivas con los cuchillos del maestro cocinero. [1] : 2 Las actualizaciones destructivas no se pueden deshacer y, por lo tanto, no deben usarse a menos que esté seguro de que el valor anterior ya no es necesario. Sin embargo, las actualizaciones destructivas también pueden permitir una eficiencia que no se puede obtener con otras técnicas. Por ejemplo, una estructura de datos que usa una matriz y actualizaciones destructivas puede ser reemplazada por una estructura de datos similar donde la matriz es reemplazada por un mapa , una lista de acceso aleatorio o un árbol balanceado , que admite una implementación puramente funcional. Pero el costo de acceso puede aumentar de tiempo constante a tiempo logarítmico . [ cita requerida ]
Asegurarse de que una estructura de datos sea puramente funcional
Una estructura de datos nunca es inherentemente funcional. Por ejemplo, una pila se puede implementar como una lista enlazada individualmente . Esta implementación es puramente funcional siempre que las únicas operaciones en la pila devuelvan una nueva pila sin alterar la pila anterior. Sin embargo, si el lenguaje no es puramente funcional, es posible que el sistema de tiempo de ejecución no pueda garantizar la inmutabilidad. Esto está ilustrado por Okasaki, [1] : 9-11 donde muestra que la concatenación de dos listas enlazadas individualmente todavía se puede hacer usando una configuración imperativa. [ cita requerida ]
Para garantizar que una estructura de datos se utilice de forma puramente funcional en un lenguaje funcional impuro, se pueden utilizar módulos o clases para garantizar la manipulación a través de funciones autorizadas únicamente. [ cita requerida ]
Uso de estructuras de datos puramente funcionales
Uno de los desafíos centrales en la adaptación del código existente para usar estructuras de datos puramente funcionales radica en el hecho de que las estructuras de datos mutables proporcionan "salidas ocultas" para las funciones que las usan. Reescribir estas funciones para usar estructuras de datos puramente funcionales requiere agregar estas estructuras de datos como salidas explícitas.
Por ejemplo, considere una función que acepta una lista mutable, inserta un elemento en la lista y devuelve la longitud de la nueva lista. En un entorno puramente funcional, la inserción de un nuevo elemento en la lista produce una nueva lista, pero no actualiza la original. Por lo tanto, para que sea útil, es probable que una versión puramente funcional de esta función tenga que devolver tanto la longitud de la lista como la nueva lista en sí. En el caso más general, un programa convertido de esta manera debe devolver el "estado" o "almacenamiento" del programa como un resultado adicional de cada llamada de función. Se dice que un programa de este tipo está escrito en estilo de paso de tienda .
Ejemplos de
Aquí hay una lista de estructuras de datos abstractas con implementaciones puramente funcionales:
- Pila (primero en entrar, último en salir) implementado como una lista enlazada individualmente ,
- Cola, implementada como una cola en tiempo real ,
- Cola de dos extremos, implementada como una cola de dos extremos en tiempo real ,
- (Multi) conjunto de elementos ordenados y mapa indexado por claves ordenadas, implementado como un árbol rojo-negro , o más generalmente por un árbol de búsqueda ,
- Cola de prioridad , implementada como cola Brodal
- Lista de acceso aleatorio, implementada como una lista de acceso aleatorio binaria sesgada
- Consing de hachís
- Cremallera (estructura de datos)
Diseño e implementación
En su libro Estructuras de datos puramente funcionales , el científico informático Chris Okasaki describe las técnicas utilizadas para diseñar e implementar estructuras de datos puramente funcionales, un pequeño subconjunto de las cuales se resume a continuación.
Pereza y memorización
La evaluación perezosa es particularmente interesante en un lenguaje puramente funcional [1] : 31 porque el orden de la evaluación nunca cambia el resultado de una función. Por lo tanto, la evaluación perezosa se convierte naturalmente en una parte importante de la construcción de estructuras de datos puramente funcionales. Permite que se realice un cálculo solo cuando su resultado es realmente necesario. Por lo tanto, el código de una estructura de datos puramente funcional puede, sin pérdida de eficiencia, considerar de manera similar los datos que se usarán de manera efectiva y los datos que se ignorarán. El único cálculo requerido es para el primer tipo de datos; eso es lo que realmente se realizará. [ cita requerida ]
Una de las herramientas clave en la construcción de estructuras de datos eficientes y puramente funcionales es la memorización. [1] : 31 Cuando se realiza un cálculo, se guarda y no es necesario realizarlo una segunda vez. Esto es particularmente importante en implementaciones perezosas; las evaluaciones adicionales pueden requerir el mismo resultado, pero es imposible saber qué evaluación lo requerirá primero. [ cita requerida ]
Análisis y programación amortizados
Algunas estructuras de datos, incluso aquellas que no son puramente funcionales como las matrices dinámicas , admiten operaciones que son eficientes la mayor parte del tiempo (p. Ej., Tiempo constante para matrices dinámicas) y rara vez ineficientes (p. Ej., Tiempo lineal para matrices dinámicas). La amortización se puede utilizar para demostrar que el tiempo medio de ejecución de las operaciones es eficiente. [1] : 39 Es decir, las pocas operaciones ineficientes son bastante raras y no cambian la evolución asintótica de la complejidad del tiempo cuando se considera una secuencia de operaciones. [ cita requerida ]
En general, tener operaciones ineficientes no es aceptable para estructuras de datos persistentes, porque esta misma operación se puede llamar muchas veces. No es aceptable ni para tiempo real ni para sistemas imperativos, donde el usuario puede requerir que el tiempo que toma la operación sea predecible. Además, esta imprevisibilidad complica el uso del paralelismo . [1] : 83 [ cita requerida ]
Para evitar esos problemas, algunas estructuras de datos permiten posponer la operación ineficiente; esto se denomina programación . [1] : 84 El único requisito es que el cálculo de la operación ineficiente debe finalizar antes de que su resultado sea realmente necesario. Una parte constante de la operación ineficiente se realiza simultáneamente con la siguiente llamada a una operación eficiente, de modo que la operación ineficaz ya se realiza totalmente cuando se necesita, y cada operación individual sigue siendo eficiente. [ aclaración necesaria ]
Ejemplo: cola
Las colas amortizadas [1] : 65 [1] : 73 se componen de dos listas unidas: la delantera y la trasera invertida. Los elementos se agregan a la lista posterior y se eliminan de la lista frontal. Además, siempre que la cola delantera está vacía, la cola trasera se invierte y se convierte en la delantera, mientras que la cola trasera se vacía. La complejidad del tiempo amortizado de cada operación es constante. Cada celda de la lista se agrega, se invierte y se elimina como máximo una vez. Para evitar una operación ineficiente en la que se invierte la lista posterior, las colas en tiempo real agregan la restricción de que la lista posterior es tan larga como la lista frontal. Para asegurarse de que la lista posterior sea más larga que la lista anterior, la lista anterior se agrega a la lista posterior y se invierte. Dado que esta operación es ineficaz, no se realiza de inmediato. En cambio, se distribuye entre las operaciones posteriores. Por lo tanto, cada celda se calcula antes de que sea necesaria, y la nueva lista frontal se calcula totalmente antes de que sea necesario llamar a una nueva operación ineficiente. [ cita requerida ]
Ver también
- Estructura de datos persistente
Referencias
- ^ a b c d e f g h i j k Estructuras de datos puramente funcionales por Chris Okasaki , Cambridge University Press , 1998, ISBN 0-521-66350-4
enlaces externos
- Tesis sobre estructuras de datos puramente funcionales de Chris Okasaki (formato PDF)
- Hacer persistentes las estructuras de datos por James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan (PDF)
- Listas completamente persistentes con catenation por James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)
- Estructuras de datos persistentes del curso MIT OpenCourseWare Algoritmos avanzados
- ¿Qué hay de nuevo en las estructuras de datos puramente funcionales desde Okasaki? en Stack Exchange de informática teórica