Una cremallera es una técnica de representación de una estructura de datos agregada de manera que sea conveniente para escribir programas que recorren la estructura de manera arbitraria y actualizan 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 de buffer de espacio que a veces se usa con matrices.
La técnica de cremallera es general en el sentido de que se puede adaptar 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 para un profano de un árbol con cremallera sería un sistema de archivos informático normal 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 cuando se realizan cambios (funcionales) en una estructura de datos, donde se devuelve una nueva estructura de datos ligeramente modificada a partir 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 pueden expresarse como la estructura generada por unas pocas operaciones constructoras primitivas u operaciones de observación. Entre ellas se incluye 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 valor xdelante de lista L.Una lista como es, [1, 2, 3]por lo tanto, la declaración Cons(1, Cons(2, Cons(3, Empty))). Es posible describir la ubicación en una lista de este tipo 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))))un Cons(2, L)y Cons(1, L)se requeriría una operación para reconstruir la lista en relación con la posición X, también conocida como Cons( X, Cons(4, Empty)). Este registro junto con la ubicación se denomina representación comprimida de la lista o cremallera de lista.
Para ser claros, una ubicación en la lista no es solo el número de Consoperaciones, sino también toda la otra información sobre ellas Cons; en este caso, los valores que deben volver a conectarse. 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 reconstruir la lista original comenzando desde [3, 4].
Un zipper de lista siempre representa la estructura de datos completa. Sin embargo, esta información se obtiene desde la perspectiva de una ubicación específica dentro de esa estructura de datos. En consecuencia, un zipper de lista es un par que consta tanto de la ubicación como contexto o punto de partida, como de un registro o ruta que permite la reconstrucción a partir de esa ubicación de partida. En particular, el zipper de lista [1, 2, 3, 4]en la ubicación de "3" puede representarse como ([2, 1], [3, 4]). Ahora bien, si "3" se cambia a "10", el zipper de lista se convierte en ([2, 1], [10, 4]). La lista puede entonces reconstruirse de manera eficiente: [1, 2, 10, 4]o recorrerse otras ubicaciones hasta .
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, la aplicación de 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 los contextos de una cremallera se puede construir mediante una transformación del tipo original que está estrechamente relacionado con la derivada del cálculo a través de la descategorización . Los tipos recursivos a partir de los cuales se forman las cremalleras se pueden ver como el punto mínimo fijo de un constructor de tipo unario de tipo . Por ejemplo, con un constructor de tipo de orden superior que construye el punto mínimo 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 adición corresponden a tipos de función , tipos de producto y tipos de suma respectivamente, mientras que los números naturales etiquetan los tipos finitos ; de esta manera, los constructores de tipo se parecen a las funciones polinómicas en . [2]
La derivada de un constructor de tipos puede, por tanto, formarse mediante esta analogía sintáctica: para el ejemplo de un árbol ternario no etiquetado, la derivada de su constructor de tipos sería equivalente a , análogamente 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 tipo se puede calcular como
Por lo tanto, el tipo de contexto 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, una cremallera para un árbol de tipo consta de dos partes: una lista de contextos de tipo del nodo actual y 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 foco o un cursor que se utiliza para navegar en algún conjunto de datos, ya que su semántica refleja la de moverse 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 en el lugar (quizás después de clonarla en profundidad , 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 al capturar 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 de recorrido para cualquier estructura de datos, pero esto es opcional: se puede utilizar cualquier función de recorrido adecuada).
Sin embargo, la cremallera genérica implica una inversión de control , por lo que algunos usos de la misma requieren una máquina de estados (o equivalente) para realizar un seguimiento de qué hacer a continuación.
