haskell - recursivas - ¿Por qué recursivo `let` hace que el espacio sea efciente?

funciones recursivas ejemplos

Question

Encontré esta afirmación mientras estudiaba la Programación reactiva funcional, de "Tapar una fuga de espacio con una flecha" por Hai Liu y Paul Hudak (página 5):

Suppose we wish to define a function that repeats its argument indefinitely:

    repeat x = x : repeat x

or, in lambdas:

    repeat = λx → x : repeat x

This requires O(n) space. But we can achieve O(1) space by writing instead:

    repeat = λx → let xs = x : xs
                  in xs

La diferencia aquí parece pequeña pero impulsa enormemente la eficiencia del espacio. ¿Por qué y cómo sucede? La mejor conjetura que he hecho es evaluarlos a mano:

    r = /x -> x: r x
    r 3

    -> 3: r 3 
    -> 3: 3: 3: ........
    -> [3,3,3,......]

Como se indicó anteriormente, tendremos que crear infinitos nuevos thunk para estas recursiones. Luego trato de evaluar el segundo:

    r = /x -> let xs = x:xs in xs
    r 3

    -> let xs = 3:xs in xs
    -> xs, according to the definition above: 
    -> 3:xs, where xs = 3:xs
    -> 3:xs:xs, where xs = 3:xs

En la segunda forma, aparece el xs y se puede compartir entre cada lugar que ocurre, así que supongo que es por eso que solo podemos requerir O(1) espacios en lugar de O(n) . Pero no estoy seguro de si estoy en lo cierto o no.

Por cierto: la palabra clave "compartido" proviene de la misma página de papel 4:

El problema aquí es que las reglas estándar de evaluación de llamada por necesidad no pueden reconocer que la función:

f = λdt → integralC (1 + dt) (f dt) 

es lo mismo que:

f = λdt → let x = integralC (1 + dt) x in x

La definición anterior hace que el trabajo se repita en la llamada recursiva a f, mientras que en el último caso el cálculo se comparte.

Answer 1

En pocas palabras, las variables se comparten, pero las aplicaciones de funciones no lo son. En

repeat x = x : repeat x

es una coincidencia (desde la perspectiva del lenguaje) que la llamada (co) recursiva a repetir sea con el mismo argumento. Entonces, sin una optimización adicional (que se llama transformación de argumento estático), la función se llamará una y otra vez.

Pero cuando escribes

repeat x = let xs = x : xs in xs

no hay llamadas a funciones recursivas. Tomas una x y construyes un valor xs cíclico usándola. Todo el intercambio es explícito.

Si quieres entenderlo de manera más formal, debes familiarizarte con la semántica de la evaluación perezosa, como A Natural Semantics for Lazy Evaluation .

Answer 2

Es más fácil de entender con imágenes:

• La primera versión

  repeat x = x : repeat x

  crea una cadena de (:) constructores que terminan en un thunk que se reemplazará con más constructores a medida que los exija. Por lo tanto, O (n) espacio.

• La segunda versión

  repeat x = let xs = x : xs in xs

  usa let para "atar el nudo", creando un único (:) constructor que se refiere a sí mismo.

Answer 3

Tu intuición acerca de que xs se comparte es correcta. Para replantear el ejemplo del autor en términos de repetición, en lugar de integral, cuando escribe:

repeat x = x : repeat x

el lenguaje no reconoce que la repeat x a la derecha es la misma que el valor producido por la expresión x : repeat x . Mientras que si escribes

repeat x = let xs = x : xs in xs

está creando explícitamente una estructura que, cuando se evalúa, tiene el siguiente aspecto:

{hd: x, tl:|}
^          |
 /________/