online - haskell shampoo

¿Por qué esta versión de ''fix'' es más eficiente en Haskell?

Question

En Haskell, esta es una definición simple (ingenua) de un punto fijo

fix :: (a -> a) -> a
fix f = f (fix f)

Pero, aquí es cómo Haskell realmente lo implementa (más eficiente)

fix f = let x = f x in x

Mi pregunta es ¿por qué el segundo es más eficiente que el primero?

Answer 1

Creo que esto ya se ha pedido, pero no pude encontrar la respuesta. La razón es que la primera versión.

fix f = f (fix f)

Es una función recursiva, por lo que no puede ser en línea y luego optimizada. Del manual de GHC :

Por ejemplo, para una función auto-recursiva, el interruptor de bucle solo puede ser la función en sí, por lo que un pragma INLINE siempre se ignora.

Pero

fix f = let x = f x in x

no es recursivo, la recursión se mueve al enlace let , por lo que es posible alinearlo.

Actualización: hice algunas pruebas y aunque la versión anterior no está en línea mientras que la última sí lo hace, no parece ser crucial para el rendimiento. Así que las otras explicaciones (un solo objeto en el montón frente a la creación de una cada iteración) parecen ser más precisas.

Answer 2

La fix lenta llama f en cada paso de recursión, mientras que la rápida llama f exactamente una vez. Se puede visualizar con trazado:

import Debug.Trace

fix  f = f (fix f)
fix'' f = let x = f x in x

facf :: (Int -> Int) -> Int -> Int
facf f 0 = 1
facf f n = n * f (n - 1)

tracedFacf x = trace "called" facf x

fac  = fix tracedFacf
fac'' = fix'' tracedFacf

Ahora intenta correr un poco:

> fac 3
called
called
called
called
6
> fac'' 3
called
6

Más detalladamente, si let x = fx in x se asigna un thunk perezoso para x , y un puntero a este thunk se pasa a f . En la primera fix'' f evaluación fix'' f , se evalúa el procesador y todas las referencias a él (aquí específicamente: la que pasamos a f ) se redirigen al valor resultante. Simplemente sucede que a x se le asigna un valor que también contiene una referencia a x .

Admito que esto puede ser más bien alucinante. Es algo a lo que uno debería acostumbrarse cuando se trabaja con la pereza.

Answer 3

No creo que esto siempre (o necesariamente siempre) te ayude cuando llamas a fix con una función que toma dos argumentos para producir una función que toma un argumento. Tendrías que ejecutar algunos puntos de referencia para ver. ¡Pero también puedes llamarlo con una función tomando un argumento!

fix (1 :)

Es una lista enlazada circular . Usando la definición ingenua de fix , sería una lista infinita, con nuevas piezas construidas perezosamente a medida que la estructura es forzada.