Una cremallera es una técnica de representación de una estructura de datos agregada para que sea conveniente para escribir programas que atraviesan 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 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 lego 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).
Ejemplo: recorrido de lista bidireccional
Muchas estructuras de datos comunes en la 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:
Empty
construye una lista vacía,Cons(x, L)
construye una lista anteponiendo o concatenando valorx
delante de la listaL
.
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 Cons
operaciones 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 Cons
operaciones, sino también toda la otra información sobre ellas Cons
; en este caso, los valores que deben volver a conectarse. 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 [X, 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 cremallera de lista es un par que consta tanto de la ubicación como contexto o punto de partida, como de una grabación o ruta que permite la reconstrucción desde esa ubicación de partida. En particular, la cremallera de lista de [1, 2, 3, 4]
en la ubicación de "3" se puede representar como ([2, 1], [3, 4])
. Ahora, si "3" se cambia a "10", entonces la cremallera de lista se convierte en ([2, 1], [10, 4])
. A continuación, la lista puede reconstruirse de manera eficiente: [1, 2, 10, 4]
u otras ubicaciones atravesadas.
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.
Contextos y diferenciación
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 la descategorificació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.. 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 etiqueta puede tener la forma . Aquí, la notación de exponenciación, multiplicación y suma corresponden a tipos de funciones , tipos de productos 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 polinomiales en. [2]
Por lo tanto, la derivada de un constructor de tipos se puede formar a través de 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 forma análoga al uso de las reglas de la suma y la potencia en el cálculo diferencial. El tipo de contextos de una cremallera sobre un tipo original. es equivalente a la derivada del constructor de tipo 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 tipo o contener un valor de tipo :
La derivada parcial del constructor de tipo se puede calcular para ser
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
- un valor booleano de tipo, expresando si el nodo actual es el hijo izquierdo o derecho de su nodo padre;
- un valor de tipo , la etiqueta del padre del nodo actual; y
- el hermano de tipo del nodo , el subárbol contenido por la otra rama del padre del nodo actual.
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 antepasados hasta el nodo raíz, y el subárbol de tipo que contiene el nodo actual.
Usos
La cremallera se usa a menudo cuando existe algún concepto de enfoque o de moverse 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
- Xmonad , para gestionar el enfoque y la ubicación de las ventanas
- Los artículos de Huet cubren un editor estructural [4] 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; garantizado estáticamente el modo de aislamiento de lectura más fuerte y repetible para los clientes; copia en escritura generalizada para archivos y directorios; función transversal incorporada y el comportamiento correcto para las referencias cíclicas de directorios ". [5]
- Clojure tiene un amplio soporte para cremalleras. [6]
Alternativas y extensiones
Modificación directa
En un lenguaje de programación no puramente funcional, puede ser más conveniente simplemente atravesar la estructura de datos original y modificarla directamente (quizás después de una clonación profunda , para evitar afectar otro código que pueda tener una referencia a él).
Cremallera genérica
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 de Haskell dado en la referencia usa programación genérica para generar una función transversal para cualquier estructura de datos, pero esto es opcional; se puede usar cualquier función transversal adecuada).
Sin embargo, Generic Zipper implica la inversión de control , por lo que algunos usos requieren una máquina de estado (o equivalente) para realizar un seguimiento de lo que se debe hacer a continuación.
Referencias
- ^ Huet 1997
- ^ Joyal, André (1981), "Une théorie combinatoire des séries formelles", Avances en matemáticas 42: 1-82.
- ^ McBride, Conor (2001), "La derivada de un tipo regular es su tipo de contextos de un agujero"
- ^ Hinze, Ralf; Jeuring, Johan (2001). "Perla funcional: Tejer una red". Revista de programación funcional . 11 (6): 681–689. doi : 10.1017 / S0956796801004129 . ISSN 0956-7968 .
- ^ Cremallera genérica: el contexto de un recorrido
- ^ jafingerhut (22 de octubre de 2010). "clojure.zip/zipper" . ClojureDocs . Consultado el 15 de junio de 2013 .
- ^ Chung-chieh Shan, Oleg Kiselyov (17 de agosto de 2008). "De caminar a cerrar la cremallera, parte 1" . Consultado el 29 de agosto de 2011 .
- ^ Chung-chieh Shan, Oleg Kiselyov (17 de agosto de 2008). "De caminar a cerrar la cremallera, parte 2" . Consultado el 29 de agosto de 2011 .
- ^ Chung-chieh Shan, Oleg Kiselyov (17 de agosto de 2008). "De caminar a cerrar la cremallera, parte 3" . Consultado el 29 de agosto de 2011 .
Otras lecturas
- Huet, Gerard (septiembre de 1997). "Perla funcional: la cremallera" (PDF) . Revista de programación funcional . 7 (5): 549–554. doi : 10.1017 / s0956796897002864 .
- Hinze, Ralf y col. "Tipos de datos indexados por tipo" . 23 de julio de 2003
enlaces externos
- Cremallera
- Teseo y la cremallera
- "Roll Your Own Window Manager: seguimiento del enfoque con una cremallera"
- Definición
- "Un gráfico de flujo de control aplicativo basado en la cremallera de Huet"
- Tipos infinitesimales