Una cremallera es una técnica de representar una estructura de datos agregada de modo que sea conveniente para escribir programas que atraviesen la estructura de manera arbitraria 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 de tampón de espacios que a veces se usa con matrices.
La técnica de la 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 se denominan normalmente "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 de computadora 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 pueden expresarse como la estructura generada por unas pocas operaciones de constructor primitivas u operaciones de observador . Estos incluyen la estructura de listas finitas, que se pueden generar mediante dos operaciones:
Una lista como [1, 2, 3]es, por tanto, la declaración Cons(1, Cons(2, Cons(3, Empty))). Es posible describir la ubicación en una 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 desde esa ubicación en particular. Por ejemplo, en Cons(1, Cons(2, Cons( X, Cons(4, Empty))))a Cons(2, L)y Cons(1, L)se requeriría una operación para reconstruir la lista relativa a la posición X, también conocida como Cons( X, Cons(4, Empty)). Esta grabación 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 reconectarse. Aquí, estos valores se pueden representar convenientemente en una lista separada en el orden de aplicación desde la ubicación de destino. Específicamente, a partir del 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].