En la lectura de las cosas a veces me encuentro con la expresión “atar el nudo” Haskell relacionado con el, creo que entiendo lo que lo hace, pero no cómo .Explicación de “atar el nudo”
Entonces, ¿hay alguna explicación buena, básica y fácil de entender de este concepto?
Atar el nudo es una solución al problema de las estructuras de datos circulares. En los lenguajes imperativos, usted construye una estructura circular creando primero una estructura no circular, y luego regresando y arreglando los punteros para agregar la circularidad.
Digamos que quería una lista circular de dos elementos con los elementos "0" y "1". Parecería imposible de construir porque si creas el nodo "1" y luego creas el nodo "0" para apuntar a él, no puedes regresar y arreglar el nodo "1" para señalar el nodo "0" . Entonces, tienes una situación de huevo y gallina donde ambos nodos deben existir antes de poder crearlos.
Así es como lo haces en Haskell. Considere el siguiente valor:
alternates = x where
x = 0 : y
y = 1 : x
En un lenguaje no perezosos este será un bucle infinito debido a la recursividad sin terminar. Pero en la evaluación perezosa de Haskell hace lo correcto: genera una lista circular de dos elementos.
Para ver cómo funciona en la práctica, piense en lo que sucede en el tiempo de ejecución. La implementación usual "thunk" de la evaluación perezosa representa una expresión no evaluada como una estructura de datos que contiene un puntero de función más los argumentos a pasar a la función. Cuando esto se evalúa, el thunk se reemplaza por el valor real para que las referencias futuras no tengan que volver a llamar a la función.
Cuando toma el primer elemento de la lista, 'x' se evalúa hasta un valor (0, & y), donde el bit "& y" es un puntero al valor de 'y'. Como 'y' no se ha evaluado, actualmente es un thunk. Cuando toma el segundo elemento de la lista, la computadora sigue el enlace de x a este procesador y lo evalúa. Evalúa a (1, & x), o en otras palabras, un puntero al valor 'x' original. Entonces ahora tiene una lista circular en la memoria. El programador no necesita reparar los indicadores de retroceso porque el mecanismo de evaluación perezosa lo hace por usted.
¡Esto fue fácil! Creo que la siguiente pregunta es: ¿cómo insertar algo en una lista doblemente vinculada en Haskell? – Alexey
@Alexey - La respuesta básica es: usted hace una copia de la lista completa con el elemento insertado agregado. Las estructuras de datos de Haskell no son mutables, por lo que tendemos a no utilizar mucho las listas con doble enlace. –
He encontrado algunas discusiones, charlas y artículos sobre este tema en Internet y estoy tratando de aprender de ellos, pero su respuesta básica no me parece convincente: si copia un solo nodo de una lista doblemente vinculada en su realización, debe copiar toda la lista, y por lo tanto no puede agregarle nada. – Alexey
No es exactamente lo que usted solicitó, y no está directamente relacionado con Haskell, pero el artículo de Bruce McAdam That About Wraps It Up aborda este tema en gran amplitud y profundidad. La idea básica de Bruce es usar un operador de nudo explícito llamado llamado WRAP en lugar de implícito nudo-atar que se realiza automáticamente en Haskell, OCaml y algunos otros idiomas. El documento tiene muchos ejemplos entretenidos , y si está interesado en anudar el nudo, creo que se sentirá mucho mejor con el proceso.
Marque [aquí] (http://www.haskell.org/haskellwiki/Tying_the_Knot). – EBGreen
O [aquí] (http://soontobehaskells.com/and-now). :) – Alexey