Una cremallera es una técnica para representar una estructura de datos agregados de manera que sea conveniente para escribir programas que atraviesen la estructura arbitrariamente y actualicen su contenido, especialmente en lenguajes de programación puramente funcionales . La cremallera fue descrita por Gérard Huet en 1997. [1] Incluye y generaliza la técnica del buffer de espacio que a veces se usa con matrices.
La técnica de cremallera es general en el sentido de que puede adaptarse a listas , árboles y otras estructuras de datos definidas de forma recursiva . Estas estructuras de datos modificadas suelen denominarse "un árbol con cremallera" o "una lista con cremallera" para enfatizar que la estructura es conceptualmente un árbol o una lista, mientras que la cremallera es un detalle de la implementación.
La explicación de un profano para un árbol con cremallera sería un sistema de archivos informático ordinario con operaciones para ir al padre (a menudo cd ..) y la posibilidad de ir hacia abajo ( cd subdirectory). La cremallera es el puntero a la ruta actual. Detrás de escena, las cremalleras son eficientes al realizar cambios (funcionales) en una estructura de datos, donde se devuelve una estructura de datos nueva, ligeramente modificada, de una operación de edición (en lugar de realizar un cambio en la estructura de datos actual).
Muchas estructuras de datos comunes en informática se pueden expresar como la estructura generada por unas pocas operaciones primitivas de constructor u operaciones de observador. Estos incluyen la estructura de listas finitas, que pueden generarse mediante dos operaciones:
Emptyconstruye una lista vacía,Cons(x, L)construye una lista anteponiendo o concatenando un valor xdelante de la lista L.Una lista como la que [1, 2, 3]por tanto es la declaración Cons(1, Cons(2, Cons(3, Empty))). Es posible describir la ubicación en dicha lista como el número de pasos desde el principio de la lista hasta la ubicación de destino. Más formalmente, una ubicación en la lista es el número de Consoperaciones necesarias para reconstruir la lista completa a partir de esa ubicación en particular. Por ejemplo, en Cons(1, Cons(2, Cons( X, Cons(4, Empty))))ay se requeriría Cons(2, L)una operación para reconstruir la lista relativa a la posición X, también conocida como . Esta grabación junto con la ubicación se denomina representación comprimida de la lista o cremallera de lista.Cons(1, L)Cons( X, Cons(4, Empty))
Para ser claros, una ubicación en la lista no es sólo el número de Consoperaciones, sino también toda la demás información sobre ellas Cons; en este caso, los valores que deben reconectarse. Aquí, estos valores pueden representarse convenientemente en una lista separada en el orden de aplicación desde la ubicación de destino. Específicamente, desde el contexto de "3" en la lista [1, 2, 3, 4], una grabación (comúnmente denominada 'ruta') podría representarse como [2, 1]donde Cons(2, L)se aplica seguido de (Cons 1, L)para reconstituir la lista original a partir de [3, 4].
Una cremallera de lista siempre representa toda la estructura de datos. Sin embargo, esta información proviene de la perspectiva de una ubicación específica dentro de esa estructura de datos. En consecuencia, una lista-cremallera es un par que consta tanto de la ubicación como contexto o punto de partida, como de un registro o camino que permite la reconstrucción desde esa ubicación inicial. En particular, la cremallera de lista [1, 2, 3, 4]en la ubicación de "3" puede representarse como ([2, 1], [3, 4]). Ahora, si "3" se cambia a "10", entonces el zip de lista se convierte en ([2, 1], [10, 4]). La lista puede entonces reconstruirse eficientemente [1, 2, 10, 4]o atravesar otras ubicaciones.
Con la lista representada de esta manera, es fácil definir operaciones relativamente eficientes en estructuras de datos inmutables como listas y árboles en ubicaciones arbitrarias. En particular, aplicar la transformación de cremallera a un árbol facilita la inserción o eliminación de valores en cualquier ubicación particular del árbol.
El tipo de contextos de una cremallera se puede construir mediante una transformación del tipo original que está estrechamente relacionada con la derivada del cálculo mediante decategorificación . Los tipos recursivos a partir de los cuales se forman las cremalleras pueden verse como el punto menos fijo de un constructor de tipo unario de tipo . Por ejemplo, con un constructor de tipo de orden superior que construye el punto menos fijo de su argumento, un árbol binario sin etiquetar se puede representar como y una lista sin etiquetar puede tomar la forma . Aquí, la notación de exponenciación, multiplicación y suma corresponden a tipos de funciones , tipos de productos y tipos de sumas respectivamente, mientras que los números naturales etiquetan los tipos finitos ; de esta manera, los constructores de tipos se parecen a funciones polinómicas en . [2]
Por lo tanto, la derivada de un constructor de tipos puede formarse mediante esta analogía sintáctica: para el ejemplo de un árbol ternario sin etiquetar, la derivada de su constructor de tipos sería equivalente a , de manera análoga al uso de las reglas de suma y potencia en el cálculo diferencial. El tipo de los contextos de una cremallera sobre un tipo original es equivalente a la derivada del constructor de tipos aplicado al tipo original, . [3]
A modo de ilustración, considere la estructura de datos recursiva de un árbol binario con nodos que son nodos centinela de tipo1 o contener un valor de tipo A :
La derivada parcial del constructor de tipos se puede calcular como
Por lo tanto, el tipo de contextos de la cremallera es
Como tal, encontramos que el contexto de cada nodo hijo no centinela en el árbol binario etiquetado es un triple que consta de
En general, un zip para un árbol de tipo consta de dos partes: una lista de contextos de tipo del nodo actual y de cada uno de sus ancestros hasta el nodo raíz, y el valor de tipo que contiene el nodo actual.
La cremallera se utiliza a menudo cuando hay algún concepto de enfoque o de movimiento en algún conjunto de datos, ya que su semántica refleja la de movimiento pero de una manera funcional no destructiva.
La cremallera se ha utilizado en
En un lenguaje de programación no puramente funcional, puede ser más conveniente simplemente recorrer la estructura de datos original y modificarla directamente (tal vez después de una clonación profunda , para evitar afectar otro código que pueda contener una referencia a ella).
La cremallera genérica [7] [8] [9] es una técnica para lograr el mismo objetivo que la cremallera convencional capturando el estado del recorrido en una continuación mientras se visita cada nodo. (El código Haskell proporcionado en la referencia utiliza programación genérica para generar una función transversal para cualquier estructura de datos, pero esto es opcional; se puede utilizar cualquier función transversal adecuada).
Sin embargo, la cremallera genérica implica inversión de control , por lo que algunos usos requieren una máquina de estados (o equivalente) para realizar un seguimiento de qué hacer a continuación.
