¿Qué significa "flotante"?

Question

En la Haskell wiki I read that this:

fib = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in (map fib' [0 ..] !!) 

es más eficiente que esto:

fib x = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in map fib' [0 ..] !! x 

Porque, "En el segundo caso fib' se (re) definida para cada argumento x, lo que no puede ser flotado fuera ".

No entiendo lo que esto significa.

1. ¿Qué significa "flotado"? ¿Cómo es una optimización?
2. ¿Por qué se redefine fib' para cada invocación de fib?
3. ¿Es esto una expansión eta o no?

Answer 1

No es una muy buena explicación.

"flotaba" significa simplemente que, en:

\x -> let y = ... in z 

si ... no menciona x entonces puede ser flotaron de la lambda:

let y = ... in \x -> z 

lo que significa que solo se computará una vez, , lo que podría ahorrar mucho tiempo si ... es costoso. Sin embargo, GHC es conservador acerca de realizar optimizaciones como esta, ya que pueden presentar fugas de espacio. (Aunque es lo hace para la segunda definición si le da una firma de tipo, como señala Daniel Fischer en su respuesta.)

No se trata de optimización automática, sin embargo. El primer fragmento define fib' fuera de lambda, mientras que el segundo lo define adentro (el lambda está implícito en fib x = ..., que es equivalente a fib = \x -> ...), que es lo que dice la cita.

Incluso eso no es realmente relevante; lo relevante es que en el primer fragmento, map fib' [0 ..] ocurre fuera de la lambda, por lo que su resultado se comparte entre todas las aplicaciones de la lambda (en ese código, la "lambda" surge de la aplicación parcial de (!!)). En este último, está dentro de la lambda, y es muy probable que se vuelva a calcular para cada aplicación de fib.

El resultado final es que la implementación anterior almacena en caché los valores y, por lo tanto, es mucho más eficiente que la última. Tenga en cuenta que la eficacia del primer fragmento depende del hecho de que fib' no se repite directamente, sino a través de fib, y por lo tanto se beneficia de la memorización.

Está relacionado con la expansión eta; el último fragmento es una expansión eta de la primera. Pero la declaración que citó no explica qué está pasando en absoluto.

Tenga en cuenta que este es el comportamiento específico de la implementación, y no parte de la semántica de Haskell. Sin embargo, todas las implementaciones razonables se comportarán de esta manera.

Answer 2

ehird 's respuestas explica las cosas muy bien, sin embargo hay un punto

El resultado final es que la primera aplicación almacena en caché los valores y por lo tanto es mucho más eficiente que el segundo.

que a veces es incorrecto.

Si compila el módulo que contiene cualquiera de las definiciones con optimizaciones (he comprobado solamente O2, no -O1, y por supuesto, sólo GHC), hay varios casos a considerar:

1. la primera definición sin tipo firma
2. la segunda definición con el tipo de firma fib :: Int -> Integer
3. la primera definición con el tipo polimórfico fib :: Num a => Int -> a
4. la segunda definición sin tipo de firma
5. la segunda definición con el tipo de firma fib :: Num a => Int -> a

En el caso 1, la restricción monomorphism produce el tipo fib :: Int -> Integer y la lista map fib' [0 .. ] se comparte a través de todas las invocaciones de fib. Eso significa que si alguna vez consulta fib (10^6), tiene una lista de los primeros millones (+1) de números de Fibonacci en la memoria, y se recopilará solo cuando el recolector de basura pueda determinar que ya no se usa. Eso a menudo es una pérdida de memoria.

En el caso 2, el resultado (núcleo ing) es prácticamente idéntico al caso 1.

En el caso 4, la lista no se comparte a través de diferentes invocaciones de nivel superior de fib (por supuesto, el resultado puede tiene muchos tipos, por lo que habrá muchas listas para compartir), pero se crea una instancia por invocación de nivel superior y se reutiliza para las llamadas de fib', por lo que calcular fib n requiere O (n) adiciones y O (n^2) pasos a través la lista. Eso no es tan malo. La lista se recopila cuando el cálculo está completo, por lo que no hay pérdida de espacio.

Caso 3 es prácticamente idéntica a 4.

Caso 5, sin embargo, es peor que la recursividad ingenuo. Dado que es explícitamente polimórfico y la lista está vinculada dentro de la lambda, la lista no puede reutilizarse para las llamadas recursivas, cada llamada recursiva crea una nueva lista ...