¿Ghc transforma una lista que solo se usa una vez en un generador por razones de eficiencia?

Question

Si es así, ¿es esto parte de la optimización estándar o específica de ghc de la que podemos depender? O simplemente una optimización de la que no podemos necesariamente depender.

P.S .: Cuando probé una muestra de prueba, que parecía indicar que estaba teniendo lugar/

Prelude> let isOdd x = x `mod` 2 == 1 
Prelude> let isEven x = x `mod` 2 == 0 
Prelude> ((filter isOdd).(filter isEven)) [1..] 

mastica CPU, pero no consume mucha memoria.

Answer 1

Depende de lo que quiere decir con generador. La lista se genera de forma lenta, y como nada más hace referencia a ella, las piezas consumidas se recogen de forma casi inmediata. Como el resultado del cálculo anterior no crece, todo el cálculo se ejecuta en espacio constante. Eso no es un requisito del estándar, pero como es más difícil implementar una semántica no estricta con un comportamiento espacial diferente para ese ejemplo (y muchos vagos similares), en la práctica puede confiar en él.

Pero normalmente, la lista todavía se genera como una lista, por lo que se produce una gran cantidad de basura. En circunstancias favorables, ghc elimina la lista [1 .. ] y produce un bucle no se distribuyen:

result :: [Int] 
result = filter odd . filter even $ [1 .. ] 

(utilizando las funciones del preludio por pereza), compilados con -O2 genera el núcleo

List.result_go = 
    \ (x_ayH :: GHC.Prim.Int#) -> 
    case GHC.Prim.remInt# x_ayH 2 of _ { 
     __DEFAULT -> 
     case x_ayH of wild_Xa { 
      __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1); 
      9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int 
     }; 
     0 -> 
     case x_ayH of wild_Xa { 
      __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1); 
      9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int 
     } 
    } 

Un bucle llanura , que va del 1 al maxBound :: Int, no produce nada en el camino y [] al final. Es casi lo suficientemente inteligente como para devolver simplemente []. Tenga en cuenta que solo hay una división por 2, GHC sabe que si un Int es par, no puede ser impar, por lo que esa verificación se ha eliminado, y en ninguna rama se crea una lista no vacía (es decir, las ramas inalcanzables tienen sido eliminado por el compilador).

Answer 2

Estrictamente hablando, Haskell no especifica ningún modelo de evaluación en particular, por lo que las implementaciones son libres de implementar la semántica del lenguaje como lo deseen. Sin embargo, en cualquier implementación sensata, incluido GHC, puede confiar en que se ejecute en un espacio constante.

En GHC, cálculos como estos dan como resultado una lista con un solo enlace que termina en un thunk que representa el resto de la lista que aún no se ha evaluado. A medida que evalúa esta lista, se generará más de la lista bajo demanda, pero como el comienzo de la lista no se menciona en ningún otro lugar, las partes anteriores son inmediatamente elegibles para la recolección de basura, por lo que obtiene un comportamiento de espacio constante.

Con las optimizaciones habilitadas, es muy probable que GHC realice la deforestación aquí, optimizando la necesidad de tener una lista y el resultado será un simple bucle sin asignación.