Estructura de datos puramente funcional

En informática , una estructura de datos puramente funcional es una estructura de datos que puede implementarse directamente 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 puramente funcionales eficientes pueden requerir el uso de evaluación perezosa y memorización .

Definición

Las estructuras de datos persistentes tienen la propiedad de mantener sus versiones anteriores sin modificar. Por otro lado, las estructuras no persistentes, como los arreglos, admiten una actualización destructiva , ^{[ 1 ]} es decir, una actualización irreversible. Una vez que un programa escribe un valor en un índice del arreglo, su valor anterior ya no se puede recuperar.

Formalmente, una estructura de datos puramente funcional es una estructura de datos que puede implementarse en un lenguaje puramente funcional , como Haskell . En la práctica, significa que las estructuras de datos deben construirse utilizando únicamente estructuras de datos persistentes como tuplas, tipos suma , tipos producto y tipos básicos como enteros, caracteres y cadenas. Dicha estructura de datos es necesariamente persistente. Sin embargo, no todas las estructuras de datos persistentes son puramente funcionales. ^{[ 1 ]}^{: 16} Por ejemplo, un array persistente es una estructura de datos que es persistente y que se implementa utilizando un array, por lo que no es puramente funcional.

En el libro Estructuras de datos puramente funcionales , Okasaki compara las actualizaciones destructivas con los cuchillos de un maestro chef. ^{[ 1 ]}^{: 2} Las actualizaciones destructivas no se pueden deshacer, por lo que no deben usarse a menos que sea seguro que el valor anterior ya no se necesita. Sin embargo, las actualizaciones destructivas también pueden permitir una eficiencia que no se puede obtener usando otras técnicas. Por ejemplo, una estructura de datos que usa un arreglo y actualizaciones destructivas puede ser reemplazada por una estructura de datos similar donde el arreglo es reemplazado 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 .

Garantizar que una estructura de datos sea puramente funcional.

Una estructura de datos nunca es inherentemente funcional. Por ejemplo, una pila puede implementarse como una lista enlazada simple . Esta implementación es puramente funcional siempre que las únicas operaciones sobre la pila devuelvan una nueva pila sin modificar la anterior. Sin embargo, si el lenguaje no es puramente funcional, el sistema de tiempo de ejecución podría no ser capaz de garantizar la inmutabilidad. Esto lo ilustra Okasaki, ^{[ 1 ]}^{: 9-11,} donde muestra que la concatenación de dos listas enlazadas simples aún puede realizarse utilizando un entorno imperativo.

Para garantizar que una estructura de datos se utilice de forma puramente funcional en un lenguaje funcional impuro, se pueden usar módulos o clases para asegurar que la manipulación se realice únicamente a través de funciones autorizadas.

Utilizando estructuras de datos puramente funcionales

Uno de los principales desafíos al adaptar el código existente para usar estructuras de datos puramente funcionales radica en que las estructuras de datos mutables proporcionan "salidas ocultas" para las funciones que las utilizan. Reescribir estas funciones para usar estructuras de datos puramente funcionales requiere agregar dichas estructuras de datos como salidas explícitas.

Por ejemplo, consideremos una función que acepta una lista mutable, elimina el primer elemento de la lista y lo devuelve. En un entorno puramente funcional, eliminar un elemento de la lista produce una lista nueva y más corta, pero no actualiza la original. Por lo tanto, para ser útil, una versión puramente funcional de esta función probablemente deba devolver la nueva lista junto con el elemento eliminado. En el caso más general, un programa convertido de esta manera debe devolver el "estado" o "almacenamiento" del programa como un resultado adicional en cada llamada a la función. Se dice que dicho programa está escrito en estilo de paso de almacenamiento .

Ejemplos

Aquí hay una lista de estructuras de datos abstractas con implementaciones puramente funcionales:

Pila (primero en entrar, último en salir) implementada como una lista enlazada simple ,
Cola, implementada como una cola en tiempo real ,
Cola de doble extremo, implementada como una cola de doble extremo en tiempo real ,
(Multi)conjunto de elementos ordenados y mapa indexado por claves ordenadas, implementado como un árbol rojo-negro o, más generalmente, mediante un árbol de búsqueda .
Cola de prioridad , implementada como una cola de Brodal.
Lista de acceso aleatorio, implementada como una lista de acceso aleatorio binaria asimétrica.
Hash consing
Cremallera (estructura de datos)

Diseño e implementación

En su libro Estructuras de datos puramente funcionales , el 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 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 un cálculo se realice 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 utilizarán efectivamente 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á.

Una de las herramientas clave para construir 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 repetirlo. Esto es particularmente importante en implementaciones perezosas; evaluaciones adicionales pueden requerir el mismo resultado, pero es imposible saber qué evaluación lo requerirá primero.

Análisis y programación amortizados

Algunas estructuras de datos, incluso aquellas que no son puramente funcionales como los arreglos dinámicos , admiten operaciones que son eficientes la mayor parte del tiempo (p. ej., tiempo constante para arreglos dinámicos) y rara vez ineficientes (p. ej., tiempo lineal para arreglos dinámicos). La amortización puede entonces usarse para demostrar que el tiempo de ejecución promedio de las operaciones es eficiente. ^{[ 1 ]}^{: 39} Es decir, las pocas operaciones ineficientes son lo suficientemente raras y no cambian la evolución asintótica de la complejidad temporal cuando se considera una secuencia de operaciones.

En general, la ineficiencia en las operaciones no es aceptable para las estructuras de datos persistentes, ya que esta misma operación puede ser llamada muchas veces. Tampoco es aceptable para sistemas en tiempo real ni para sistemas imperativos, donde el usuario puede requerir que el tiempo de ejecución de la operación sea predecible. Además, esta imprevisibilidad complica el uso del paralelismo . ^{[ 1 ]}^{: 83}

Para evitar estos problemas, algunas estructuras de datos permiten posponer la operación ineficiente; esto se denomina planificación . ^{[ 1 ]}^{: 84} El único requisito es que el cálculo de la operación ineficiente finalice antes de que se necesite su resultado. Una parte constante de la operación ineficiente se ejecuta simultáneamente con la siguiente llamada a una operación eficiente, de modo que la operación ineficiente ya esté totalmente terminada cuando se necesite, y cada operación individual siga siendo eficiente.

Ejemplo: cola

Las colas amortizadas ^{[ 1 ]}^{: 65}^{[ 1 ]}^{: 73} están compuestas por dos listas enlazadas simples: la cola frontal y la cola trasera invertida. Se añaden elementos a la cola trasera y se eliminan de la cola frontal. Además, cuando la cola frontal está vacía, la cola trasera se invierte y se convierte en la cola frontal, mientras que la cola trasera se vacía. La complejidad temporal amortizada de cada operación es constante. Cada celda de la lista se añade, invierte y elimina como máximo una vez. Para evitar una operación ineficiente en la que se invierte la cola trasera, las colas en tiempo real añaden la restricción de que la cola trasera solo tenga la misma longitud que la cola frontal. Para garantizar que la cola frontal sea más larga que la cola trasera, esta última se invierte y se añade a la cola frontal. Dado que esta operación es ineficiente, no se realiza inmediatamente. En su lugar, se distribuye entre las operaciones subsiguientes. De este modo, cada celda se calcula antes de que sea necesaria, y la nueva cola frontal se calcula completamente antes de que sea necesario llamar a una nueva operación ineficiente.

Véase también

Estructura de datos persistente

Referencias

1 2 3 4 5 6 7 8 9 10 11 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 totalmente persistentes con concatenación por James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)
Estructuras de datos persistentes del curso Algoritmos avanzados de MIT OpenCourseWare
¿Qué novedades hay en estructuras de datos puramente funcionales desde Okasaki? (en Theoretical Computer Science Stack Exchange)

[Okasaki-book-1] 1 2 3 4 5 6 7 8 9 10 11 Estructuras de datos puramente funcionales por Chris Okasaki , Cambridge University Press , 1998, ISBN 0-521-66350-4

[ 1 ]