NoMonomorphismRestriction aiuta a preservare la condivisione?

Question

Stavo cercando di rispondere a another question riguardo al polimorfismo e alla condivisione quando mi sono imbattuto in questo strano comportamento.

In GHCi, quando mi definisco in modo esplicito una costante polimorfica, non c'è niente di condivisione, il che è comprensibile:

> let fib :: Num a => [a]; fib = 1 : 1 : zipWith (+) fib (tail fib) 
> fib !! 30 
1346269 
(5.63 secs, 604992600 bytes) 

D'altra parte, se cerco di ottenere lo stesso omettendo la firma di tipo e disabilitando la restrizione del monomorfismo, la mia costante viene improvvisamente condivisa!

> :set -XNoMonomorphismRestriction 
> let fib = 1 : 1 : zipWith (+) fib (tail fib) 
> :t fib 
fib :: Num a => [a] 
> fib !! 50 
20365011074 
(0.00 secs, 2110136 bytes) 

Perché ?!

Ugh ... Se compilato con ottimizzazioni, è veloce anche con restrizione del monomorfismo disabilitata.

Answer 1

Dando firma di tipo esplicito, si impedisce GHC dal fare alcune ipotesi circa il vostro codice. Ti faccio vedere un esempio (tratto da questo question):

foo (x:y:_) = x == y 
foo [_]  = foo [] 
foo []  = False 

Secondo GHCi, il tipo di questa funzione è Eq a => [a] -> Bool, come ci si aspetterebbe. Tuttavia, se si dichiara foo con questa firma, si otterrà l'errore "Variabile di tipo ambiguo".

Il motivo per cui questa funzione funziona solo senza una firma di tipo è a causa di come funziona il controllo della digitazione in GHC. Quando si omette una firma del tipo, si assume che foo abbia il monotipo [a] -> Bool per alcuni tipi fissi a. Una volta finito di digitare il gruppo di rilegatura, si generalizzano i tipi. Ecco dove ottieni il forall a. ....

D'altra parte, quando si dichiara una firma di tipo polimorfico, è dichiarare esplicitamente che foo è polimorfica (e quindi il tipo di [] non deve corrispondere al tipo di primo argomento) e boom, si ottiene il tipo ambiguo variabile.

Ora, sapendo questo, confrontiamo il nucleo:

fib = 0:1:zipWith (+) fib (tail fib) 
----- 
fib :: forall a. Num a => [a] 
[GblId, Arity=1] 
fib = 
    \ (@ a) ($dNum :: Num a) -> 
    letrec { 
     fib1 [Occ=LoopBreaker] :: [a] 
     [LclId] 
     fib1 = 
     break<3>() 
     : @ a 
      (fromInteger @ a $dNum (__integer 0)) 
      (break<2>() 
      : @ a 
      (fromInteger @ a $dNum (__integer 1)) 
      (break<1>() 
       zipWith 
       @ a @ a @ a (+ @ a $dNum) fib1 (break<0>() tail @ a fib1))); } in 
    fib1 

E per il secondo:

fib :: Num a => [a] 
fib = 0:1:zipWith (+) fib (tail fib) 
----- 
Rec { 
fib [Occ=LoopBreaker] :: forall a. Num a => [a] 
[GblId, Arity=1] 
fib = 
    \ (@ a) ($dNum :: Num a) -> 
    break<3>() 
    : @ a 
     (fromInteger @ a $dNum (__integer 0)) 
     (break<2>() 
     : @ a 
     (fromInteger @ a $dNum (__integer 1)) 
     (break<1>() 
      zipWith 
      @ a 
      @ a 
      @ a 
      (+ @ a $dNum) 
      (fib @ a $dNum) 
      (break<0>() tail @ a (fib @ a $dNum)))) 
end Rec } 

Con firma di tipo esplicito, come con foo sopra, GHC deve trattare fib come valore potenzialmente ricorsivo polimorficamente. Abbiamo potuto passare un po 'diverso Num dizionario per fib in zipWith (+) fib ... ea questo punto avremmo dovuto gettare la maggior parte della lista di distanza, dal momento che diversi Num diversi mezzi (+). Naturalmente, una volta compilati con le ottimizzazioni, GHC rileva che il dizionario Num non cambia mai durante le "chiamate ricorsive" e lo ottimizza.

Nel nucleo sopra, è possibile vedere che GHC fornisce effettivamente fib un dizionario Num (denominato $dNum) ancora e ancora.

Poiché fib senza firma tipo è stato ipotizzato monomorfa prima della generalizzazione di tutto il gruppo di legame era finito, le sottoparti fib hanno avuto esattamente lo stesso tipo del tutto fib. Grazie a questo, fib assomiglia:

{-# LANGUAGE ScopedTypeVariables #-} 
fib :: forall a. Num a => [a] 
fib = fib' 
    where 
    fib' :: [a] 
    fib' = 0:1:zipWith (+) fib' (tail fib') 

E perché il tipo rimane fissa, è possibile utilizzare solo quello dizionario data all'avvio.

Answer 2

Qui si utilizza fib con lo stesso tipo di argomento in entrambi i casi e ghc è abbastanza intelligente da vedere questo ed eseguire la condivisione.

Ora, se è stata utilizzata la funzione di dove può essere chiamato con diversi argomenti di tipo, e inadempienti portato a uno di quelli che sono molto diversi rispetto agli altri, quindi la mancanza di restrizione monomorfismo sarebbe morderà.

considerare l'uso del termine x = 2 + 2 polimorfico in due contesti senza la restrizione monomorfismo, dove in un contesto che si show (div x 2) e in un altro si utilizza show (x/2), in un contesto che si ottiene i Integral e Show vincoli che ti fa di default a Integer, in l'altro si ottiene un Fractional e un vincolo Show e per impostazione predefinita è Double, quindi il risultato del calcolo non è condiviso, poiché si sta lavorando con un termine polimorfico applicato a due tipi distinti. Con la limitazione del monomorfismo attivata, tenta di default una volta per qualcosa di Integrale e Frazionale e fallisce.

Intendiamoci sua Tricker per ottenere tutto questo al fuoco in questi giorni con lasciar non generalizzare, ecc