Estaba leyendo un capítulo en LYAH que realmente no tenía sentido para mí. Entiendo que las cremalleras pueden atravesar arbitrariamente una estructura similar a un árbol, pero necesito alguna aclaración al respecto. Además, ¿se pueden generalizar las cremalleras a cualquier estructura de datos?
ds.data-structures
functional-programming
tree
n_ary_crazy
fuente
fuente
Respuestas:
Una cremallera, en general, es una estructura de datos con un agujero. Las cremalleras se utilizan para atravesar / manipular estructuras de datos, y el agujero corresponde al foco actual del recorrido. Por lo general, también hay un elemento de la estructura de datos en consideración, de modo que uno tiene una cremallera (lista) y una lista o una cremallera (árbol) y un árbol. La cremallera permite al programador moverse eficientemente alrededor de la estructura de datos, incluso reemplazando el elemento en el foco. El par de la cremallera y el elemento en el foco satisfacen la restricción de que colocar el elemento en el foco en el agujero proporciona la estructura de datos original.
Las cremalleras se pueden generalizar a tipos de datos inductivos arbitrarios. El concepto se puede definir de manera indexada por tipo (ver tipos de datos indexados por tipo ). También están relacionados con la idea de la derivada de una estructura de datos , y se ha estudiado desde una perspectiva teórica de categoría .
fuente
Una cremallera es, en general, un par de cosas: es una estructura con un agujero, un foco , que representa en qué parte de la estructura te encuentras, junto con una ruta , registrando cómo llegaste a ese foco. (Este camino es el rastro de migas de pan de LYAH).
La ruta es cómo se aplican los cambios a la estructura: "ir hacia abajo, hacia la izquierda, incrementar el valor". Al aplicar repetidamente "subir" (
go_upen el artículo de Huet ) en este punto, puede volver sobre sus pasos y terminar con una nueva copia mutada de la estructura original.De hecho, pueden generalizarse a otras estructuras:
fuente