data structures - ¿Cuál es la estructura de datos de Zipper y debería usarlo?
data-structures functional-programming (4)
La pregunta es simple: no puedo entender la estructura de datos de Zipper .
Mi pregunta está relacionada con sus usos con un árbol.
Quiero entender cómo puedo cambiar el nodo del árbol usando la cremallera. Y cómo no copiar todo el árbol (o la mayor parte de él).
Por favor, aclara si me equivoco con la cremallera. Tal vez no puede ayudar con la actualización del árbol?
O, tal vez, es posible actualizar el árbol y simplemente no puedo ver el camino?
Aprende que un Haskell también tiene un gran capítulo sobre cremalleras .
Aquí hay un artículo muy bueno que explica el uso de la cremallera para un administrador de ventanas de mosaico en Haskell . El artículo de Wikipedia no es una buena referencia.
En resumen, la cremallera es un puntero o manejador de un nodo particular en una estructura de árbol o lista. La cremallera proporciona una forma natural de tomar una estructura de árbol y tratarla como si el árbol fuera "recogido" por el nodo enfocado; en efecto, obtienes un segundo árbol sin requerir copias adicionales hechas del árbol original o afectando a otros usuarios de el árbol.
El ejemplo dado muestra cómo tiene las ventanas originalmente ordenadas por ubicación en la pantalla, y luego para modelar el enfoque utiliza una cremallera apuntando a la ventana de enfoque. Obtiene un buen conjunto de operaciones O (1) como insertar y eliminar sin tener que tener un caso especial en la ventana de enfoque o escribir un código adicional.
Este artículo está relacionado con Haskell, pero también explica las cremalleras bastante bien y debería ser fácil abstraerse de los detalles de Haskell.
Comencemos con Zipper-analog para listas. Si desea modificar el enésimo elemento de una lista, toma O (n) porque debe copiar los primeros n-1 elementos. En cambio, puede mantener la lista como una estructura ((los primeros n-1 elementos invertidos) enésimo elemento (elementos restantes)). Por ejemplo, la lista (1 2 3 4 5 6) modificable en 3 se representaría como ((2 1) 3 (4 5 6)) . Ahora, puedes cambiar fácilmente el 3 a algo más. También puede mover fácilmente el foco hacia la izquierda ((1) 2 (3 4 5 6)) y hacia la derecha ((3 2 1) 4 (5 6)) .
Una cremallera es la misma idea aplicada a los árboles. Usted representa un cierto enfoque en el árbol más un contexto (hasta los padres, hasta los niños) que le da a todo el árbol una forma en la que es fácilmente modificable en el foco y es fácil mover el foco hacia arriba y hacia abajo.