Cremallera (estructura de datos)

Una cremallera es una técnica para representar una estructura de datos agregada de manera que resulte conveniente escribir programas que la recorran 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 búfer de huecos que a veces se utiliza con arreglos.

La técnica de la cremallera es general en el sentido de que puede adaptarse a listas , árboles y otras estructuras de datos definidas recursivamente . Estas estructuras de datos modificadas suelen denominarse "árbol con cremallera" o "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.

Una explicación sencilla para un no experto sobre un árbol con cremallera sería un sistema de archivos informático común con operaciones para ir al nodo padre (a menudo cd ..) y para descender ( cd subdirectory). La cremallera es el puntero a la ruta actual. Internamente, las cremalleras son eficientes al realizar cambios (funcionales) en una estructura de datos, donde se devuelve una nueva estructura de datos ligeramente modificada tras una operación de edición (en lugar de modificar 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 . Estas 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 esta [1, 2, 3]es, por lo tanto, 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 toda la lista a partir de esa ubicación particular. Por ejemplo, en Cons(1, Cons(2, Cons( X, Cons(4, Empty))))una Cons(2, L)y Cons(1, L)se requeriría una operación para reconstruir la lista con respecto a 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 lista-comprimida.

Para ser claros, una ubicación en la lista no es solo 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 comenzando desde [3, 4].

Un list-zipper siempre representa la estructura de datos completa. Sin embargo, esta información se presenta desde la perspectiva de una ubicación específica dentro de esa estructura de datos. En consecuencia, un list-zipper 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 desde esa ubicación de partida. En particular, el list-zipper en [1, 2, 3, 4]la ubicación "3" puede representarse como ([2, 1], [3, 4]). Ahora, si "3" se cambia a "10", entonces el list-zipper se convierte en ([2, 1], [10, 4]). La lista puede reconstruirse eficientemente: [1, 2, 10, 4]o recorrer 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, aplicar la transformación de cremallera a un árbol facilita la inserción o eliminación de valores en cualquier posición del mismo.

El tipo de contextos de una cremallera se puede construir mediante una operación sobre el tipo original que está estrechamente relacionada 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 pueden verse como el punto fijo mínimo de un constructor de tipo unario de tipo${\displaystyle *\rightarrow *}$Por ejemplo, con un constructor de tipo de orden superior.${\displaystyle {\text{lfp}}:(*\rightarrow *)\rightarrow *}$que construye el punto fijo más pequeño de su argumento, un árbol binario sin etiquetar puede representarse como${\displaystyle {\text{lfp}}(T\mapsto T^{2}+1)}$y una lista sin etiquetar puede tomar la forma${\displaystyle {\text{lfp}}(T\mapsto T+1)}$Aquí, la notación de exponenciación, multiplicación y suma 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 tipos se asemejan a funciones polinómicas. ^{[ 2 ]}

Por lo tanto, el derivado de un constructor de tipos puede formarse mediante esta analogía sintáctica, y la cremallera del constructor de tipos es el derivado emparejado con su tipo de elemento. De esta manera, el derivado puede verse como una cremallera con un agujero, donde se podría colocar un valor.

Consideremos el tipo de listas enlazadas simples. La estructura de datos de la lista se puede definir como${\displaystyle L(X)=1+X\times L(X)}$. Eso es,${\displaystyle L}$es un constructor de tipo que toma un tipo de elemento${\displaystyle X}$y produce el tipo de listas de ese tipo de elemento. Los dos sumandos corresponden a los dos constructores de datos para una lista. El Nilconstructor de datos, un nodo centinela que no contiene datos, está representado por el tipo de unidad.${\displaystyle 1}$y el Consconstructor se representa como un producto del elemento de cabeza.${\displaystyle X}$y la cola${\displaystyle L}$de la lista.

Bajo esta representación, la derivada${\displaystyle L'}$de${\displaystyle L}$en términos de${\displaystyle X}$es${\displaystyle L'(X)=L(X)+X\times L'(X)}$Es decir, si tenemos una lista con una cremallera y un agujero, entonces (I) el agujero es el primer elemento y el resto de la lista es una lista ordinaria (sin cremallera).${\displaystyle L(X)}$, o (II) el primer elemento está presente (${\displaystyle X}$) y el agujero está en algún otro lugar más abajo en la cola de la lista (${\displaystyle L'(X)}$). Entonces, el tipo formal de una cremallera para una lista enlazada es${\displaystyle X\times L'(X)}$, o${\displaystyle X\times (L(X)+X\times L'(X))}$Dicho de otro modo, una cremallera para una lista enlazada consiste en un elemento de esa lista e instrucciones sobre dónde colocarlo en una lista parcialmente construida.

Como otro ejemplo, consideremos la estructura de datos recursiva de un árbol binario con nodos que son nodos centinela de tipo${\displaystyle 1}$o que sean hojas que contengan un valor de algún tipo${\displaystyle X}$Podemos representar este tipo algebraicamente como${\displaystyle T(X)=1+X\times T^{2}(X)}$. La derivada en términos de${\displaystyle X}$es${\displaystyle T'(X)=T^{2}(X)+2\times X\times T(X)\times T'(X)}$Podemos leer esta notación algebraica como una cremallera con un agujero: Una cremallera para un árbol tiene el "valor faltante" en la raíz misma del árbol, dejando las dos ramas como árboles ordinarios (la${\displaystyle T^{2}(X)}$caso), o tiene el valor faltante en una de las dos ramas (${\displaystyle 2\times X\times T(X)\times T'(X)}$). En este último caso, el tipo booleano${\displaystyle 2}$indica qué rama (izquierda o derecha) contiene el agujero, y la cremallera contiene un valor para la raíz, un${\displaystyle T(X)}$para la rama completa y una${\displaystyle T'(X)}$para la rama a la que le falta un valor de tipo${\displaystyle X}$El tipo completo de una cremallera para esta estructura de árbol binario es, entonces,${\displaystyle X\times T'(X)}$, o${\displaystyle X\times (T^{2}(X)+2\times X\times T(X)\times T'(X))}$.

En general, una cremallera consta de dos partes: una colección de contextos para el nodo actual y cada uno de sus ancestros hasta el nodo raíz, y el valor que contiene el nodo actual.

La cremallera se usa a menudo cuando existe algún concepto de enfoque o un cursor que se utiliza para navegar por un conjunto de datos, ya que su semántica refleja la de moverse, pero de una manera funcional y no destructiva.

La cremallera se ha utilizado en

• Xmonad , para gestionar el enfoque y la ubicación de las ventanas.
• Los artículos de Huet tratan sobre un editor estructural ^{[ 3 ]} basado en cremalleras y un demostrador de teoremas.
• Un sistema de archivos (ZipperFS) escrito en Haskell que ofrece "...semántica transaccional; deshacer cualquier operación de archivo y directorio; instantáneas; modo de aislamiento de lectura repetible y con garantía estática para clientes; copia en escritura generalizada para archivos y directorios; función de recorrido integrada; y el comportamiento adecuado para referencias cíclicas a directorios." ^{[ 4 ]}
• Clojure tiene un amplio soporte para cremalleras. ^{[ 5 ]}

• Huet, Gerard (septiembre de 1997). "La Cremallera" (PDF) . Revista de programación funcional . 7 (5): 549– 554. doi : 10.1017/s0956796897002864 . S2CID 31179878 . 
• Hinze, Ralf; Jeuring, Johan; Löh, Andrés (mayo de 2004). "Tipos de datos indexados por tipo" . Ciencia de la programación informática . 51 ( 1– 2): 117– 151. doi : 10.1016/j.scico.2003.07.001 .

• Cremallera
• Teseo y la cremallera
• "Crea tu propio gestor de ventanas: Controla el enfoque con una cremallera"
• Definición
• "Un grafo de flujo de control aplicativo basado en la cremallera de Huet"
• Tipos infinitesimales