¿Por qué la adición de una firma de tipo polimórfico degrada el rendimiento?

Question

Aquí es una función simple para calcular los números de Fibonacci:

fib :: [Int] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

En ghci puedo calcular la serie rápidamente. De hecho, un poco de experimentación revela que el cálculo se ejecuta en tiempo aproximadamente lineal.

ghci> last $ take 100000 fib 
354224848179261915075   -- takes under a second 

si cambio de la firma de tipo a ser polimórficos en su lugar:

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

A continuación, el algoritmo se vuelve más lento. De hecho, parece que ahora se ejecuta en tiempo exponencial.

¿Cambiar a una firma de tipo polimórfico significa que la lista se vuelve a calcular por completo en cada etapa? Si es así, ¿por qué?

Answer 1

Esto se debe a la traducción del diccionario.

fib :: [Int] 

es una constante de nivel superior.

Pero esto:

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

es sólo una función de nivel superior, que se aplicará a un diccionario Num en tiempo de ejecución. De este modo:

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d)) 

tanto, si compila esto sin ninguna optimización, de modo que ninguna especialización puede suceder, usted va a terminar con fib tiempo exponencial, ya que la lista se reconstruye a partir de cero, en cada llamada a la función - Ya no es una estructura de datos vagos.

Answer 2

Sí, la firma de tipo polimórfico significa que se está recalculando en cada etapa. El núcleo producido por ghc-7.4.2 con -O2:

lvl_rcZ :: GHC.Integer.Type.Integer 
[GblId, Str=DmdType] 
lvl_rcZ = __integer 1 

Rec { 
PolyFib.fib [Occ=LoopBreaker] 
    :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W] 
[GblId, Arity=1, Str=DmdType L] 
PolyFib.fib = 
    \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) -> 
    GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.List.zipWith 
      @ a_aal 
      @ a_aal 
      @ a_aal 
      (GHC.Num.+ @ a_aal $dNum_aam) 
      (PolyFib.fib @ a_aal $dNum_aam) 
      (case PolyFib.fib @ a_aal $dNum_aam of _ { 
       [] -> GHC.List.tail1 @ a_aal; 
       : _ xs_abD -> xs_abD 
      }))) 
end Rec } 

La razón es que no es factible para almacenar en caché una lista de números de Fibonacci para cada tipo perteneciente a Num, y fib es explícitamente un valor polimórfica, por lo tanto, no se almacena en caché en absoluto.

Si desea almacenar en caché por lo menos para el cálculo de cada tipo, utilice una lista local

pfibs :: Num a => [a] 
pfibs = res 
    where 
    res = 1 : 1 : zipWith (+) res (tail res) 

hace el almacenamiento en caché para cada cálculo (por lo pfibs !! 500 por ejemplo, es rápido) ya que ahora la lista es monomórfica en cada computación Se volverá a calcular para cada consulta (a menos que la vincules con un nombre monomórfico), pero no para cada elemento de lista individual.

*PolyFib> pfibs !! 999999 :: Int 
-4249520595888827205 
(0.31 secs, 137462088 bytes)