¿El rendimiento de las funciones parciales o curriculares está bien definido en Haskell?

Question

En el siguiente código:

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l x = x == maxel 
      where maxel = maximum l 

main = do 
    let mylist = [1, 2, 3, 5] 
    let ismax = ismaxl mylist 
    --Is each call O(1)? Does each call remember maxel? 
    let c1 = ismax 1 
    let c2 = ismax 2 
    let c3 = ismax 3 
    let c5 = ismax 5 
    putStrLn (show [c1, c2, c3, c5]) 

¿El ismax función parcial, calcular el maxel? En términos prácticos, ¿alguien puede señalar una regla sobre la complejidad de las funciones parciales en Haskell? ¿DEBE el compilador solo llamar al máximo una vez en el ejemplo anterior? Dicho de otra manera, ¿mantiene una función parcial las referencias de llamadas previas para cláusulas where internas?

Tengo algunos códigos de CPU que no funcionan de manera aceptable, y estoy buscando posibles errores en mi razonamiento sobre la complejidad.

Answer 1

Como una demostración de lo que puede aprender al crear perfiles de su código Haskell, este es el resultado de algunas modificaciones menores en su código. En primer lugar, he reemplazado mylist con [0..10000000] para asegurarme de que lleva un tiempo calcular el máximo.

Aquí hay algunas líneas de la salida de perfiles, después de ejecutar esa versión:

COST CENTRE     MODULE    %time %alloc 

ismaxl       Main     55.8 0.0 
main       Main     44.2 100.0 

                 individual inherited 
COST CENTRE    MODULE   no. entries %time %alloc %time %alloc 

MAIN      MAIN   1   0 0.0 0.0 100.0 100.0 
CAF:main_c5    Main   225   1 0.0 0.0 15.6 0.0 
    main     Main   249   0 0.0 0.0 15.6 0.0 
    ismaxl    Main   250   1 15.6 0.0 15.6 0.0 
CAF:main_c3    Main   224   1 0.0 0.0 15.6 0.0 
    main     Main   246   0 0.0 0.0 15.6 0.0 
    ismaxl    Main   247   1 15.6 0.0 15.6 0.0 
CAF:main_c2    Main   223   1 0.0 0.0 14.3 0.0 
    main     Main   243   0 0.0 0.0 14.3 0.0 
    ismaxl    Main   244   1 14.3 0.0 14.3 0.0 
CAF:main_c1    Main   222   1 0.0 0.0 10.4 0.0 
    main     Main   239   0 0.0 0.0 10.4 0.0 
    ismaxl    Main   240   1 10.4 0.0 10.4 0.0 
CAF:main8    Main   221   1 0.0 0.0 44.2 100.0 
    main     Main   241   0 44.2 100.0 44.2 100.0 

Es bastante obvio recalcular la máxima aquí.

Ahora, en sustitución de ismaxl con esto:

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l = let maxel = maximum l in (== maxel) 

... y perfilado de nuevo:

COST CENTRE     MODULE    %time %alloc 

main       Main     60.5 100.0 
ismaxl       Main     39.5 0.0 

                 individual inherited 
COST CENTRE    MODULE   no. entries %time %alloc %time %alloc 

MAIN      MAIN   1   0 0.0 0.0 100.0 100.0 
CAF:main_c5    Main   227   1 0.0 0.0  0.0 0.0 
    main     Main   252   0 0.0 0.0  0.0 0.0 
    ismaxl    Main   253   1 0.0 0.0  0.0 0.0 
CAF:main_c3    Main   226   1 0.0 0.0  0.0 0.0 
    main     Main   249   0 0.0 0.0  0.0 0.0 
    ismaxl    Main   250   1 0.0 0.0  0.0 0.0 
CAF:main_c2    Main   225   1 0.0 0.0  0.0 0.0 
    main     Main   246   0 0.0 0.0  0.0 0.0 
    ismaxl    Main   247   1 0.0 0.0  0.0 0.0 
CAF:main_c1    Main   224   1 0.0 0.0  0.0 0.0 
CAF:main_ismax   Main   223   1 0.0 0.0 39.5 0.0 
    main     Main   242   0 0.0 0.0 39.5 0.0 
    ismaxl    Main   243   2 39.5 0.0 39.5 0.0 
CAF:main8    Main   222   1 0.0 0.0 60.5 100.0 
    main     Main   244   0 60.5 100.0 60.5 100.0 

... esta vez se trata de pasar la mayor parte de su tiempo en una sola llamada a ismaxl, los otros son demasiado rápidos como para darse cuenta, así que debe calcular el máximo una vez aquí.

Answer 2

No he podido encontrar ningún requisito en el Haskell Report, y de hecho GHC no parece realizar esta optimización por defecto.

que cambió su función main a

main = do 
    let mylist = [1..99999] 
    let ismax = ismaxl mylist 
    let c1 = ismax 1 
    let c2 = ismax 2 
    let c3 = ismax 3 
    let c5 = ismax 5 
    putStrLn (show [c1, c2, c3, c5]) 

espectáculos de perfiles simples (en mi viejo Pentium 4):

$ ghc a.hs 
$ time ./a.out 
[False,False,False,False] 

real 0m0.313s 
user 0m0.220s 
sys  0m0.044s 

Pero cuando cambio la definición de c2, c3 y c5 a let c2 = 2 == 99999 etc. . (dejando c1 como es), obtengo

$ ghc a.hs 
$ time ./a.out 
[False,False,False,False] 

real 0m0.113s 
user 0m0.060s 
sys  0m0.028s 

Answer 3

Aquí es una versión modificada de su código que le permitirá ver si es o no se reutiliza maxel:

import Debug.Trace 

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l x = x == maxel 
      where maxel = trace "Hello" $ maximum l 

main = do 
    let mylist = [1, 2, 3, 5] 
    let ismax = ismaxl mylist 
    --Is each call O(1)? Does each call remember maxel? 
    let c1 = ismax 1 
    let c2 = ismax 2 
    let c3 = ismax 3 
    let c5 = ismax 5 
    putStrLn (show [c1, c2, c3, c5]) 

Verás que no es maxel 'recordado' entre aplicaciones.

En general, no debe esperar que Haskell comience a hacer reducciones hasta que todos los argumentos se hayan suministrado a una función.

Por otro lado, si tiene una optimización agresiva activada, entonces es difícil predecir qué haría un compilador en particular. Pero probablemente no deberías confiar en ninguna parte del compilador que sea difícil de predecir cuando puedas reescribir fácilmente el código para hacer que lo que quieras sea explícito.

Answer 4

Construyendo otras buenas respuestas, GHC no ha estado ansioso por realizar este tipo de optimización en mi experiencia. Si no puedo hacer fácilmente algo de punto libre, a menudo he recurrido a la escritura con una mezcla de VARs encuadernados en el LHS y una lambda:

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l = \x -> x == maxel 
      where maxel = maximum l 

Particularmente no me gusta este estilo, pero garantiza que maxel se comparte entre llamadas a un ismaxl parcialmente aplicado.