haskell - Explicación de "atar el nudo"

functional-programming tying-the-knot

Question

Al leer cosas relacionadas con Haskell, a veces me cruzo con la expresión "atar el nudo", creo que entiendo lo que hace, pero no cómo .

Entonces, ¿hay alguna explicación buena, básica y simple de entender de este concepto?

Answer 1

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 perezoso, este será un ciclo infinito debido a la recursión sin terminación. 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 y), donde el bit "y 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.

Answer 2

No es exactamente lo que pediste, y no está directamente relacionado con Haskell, pero el artículo de Bruce McAdam, That About Wraps It Up, aborda este tema en una amplitud y profundidad sustanciales. La idea básica de Bruce es usar un operador explícito de nudo vinculado llamado WRAP en lugar del nudo implícito que se realiza automáticamente en Haskell, OCaml y algunos otros idiomas. El periódico tiene muchos ejemplos entretenidos , y si está interesado en hacer nudos, creo que se sentirá mucho mejor con el proceso.