Perché Haskell non è in grado di evitare una valutazione ripetuta senza la limitazione del monomorfismo?

Question

Perché Haskell non è in grado di evitare una valutazione ripetuta senza la limitazione del monomorfismo?

#1 da (10 voti)

14

Ho appena finito learnyouahaskell l'altro giorno, e stavo cercando di dare un senso alla restrizione del monomorfismo, come descritto da Haskell Wiki . Penso di capire come il MR possa prevenire valutazioni ripetute, ma non riesco a capire perché quelle ripetute valutazioni non possono essere evitate con mezzi molto più diretti.

L'esempio specifico che ho in mente è quello usato dalla wiki:

f xs = (len,len)
  where
    len = genericLength xs

dove genericLength è di tipo Num a => [b] -> a .

Ovviamente, genericLength xs deve essere calcolato una sola volta per valutare (len,len) , poiché è la stessa funzione con gli stessi argomenti. E non abbiamo bisogno di vedere alcuna invocazione di f per saperlo. Allora perché Haskell non può fare questa ottimizzazione senza introdurre una regola come MR?

La discussione su quella pagina wiki mi dice che ha qualcosa a che fare con il fatto che Num è un typeclass piuttosto che un tipo concreto, ma anche così, non dovrebbe essere ovvio in fase di compilazione che una funzione pura restituirebbe lo stesso valore - e quindi lo stesso tipo concreto di Num - quando gli stessi argomenti vengono dati due volte?

type-systems optimization haskell

posta Ixrec 06.05.2015 - 21:50

fonte

1 risposta

Leggi altre domande sui tag type-systems optimization haskell

Come eseguire test API esterni (blackbox) Considerazioni su quale versione di Java deve essere eseguita in produzione

score 10 · Accepted Answer

È lo stesso nome di funzione, con gli stessi argomenti, ma potenzialmente diversi tipi di ritorno e implementazioni, perché è polimorfico. Ciò significa che se viene chiamato in un contesto che si aspetta un tipo di ritorno (Int, MyWeirdCustomNumType) , deve valutarlo due volte, perché l'implementazione di (+) in Int è completamente diversa dall'implementazione di (+) in MyWeirdCustomNumType . È necessario eseguire codice fisicamente diverso a un certo punto.

Ecco perché è importante che Num sia una classe di tipo. Significa che hai diverse implementazioni per diversi tipi. Significa anche che se f è in una libreria, non sa al momento della compilazione tutte le combinazioni di tipi che potrebbe dover essere restituito.

Quindi, sì, è necessario vedere le invocazioni di f per sapere quali tipi di ritorno utilizzare. La maggior parte delle volte, ci si aspetterebbe che siano uguali, motivo per cui inseriscono la restrizione del monomorfismo di default. Può essere spento per quelle rare occasioni in cui non lo fai. In pratica, i programmatori non tendono comunque ad abbandonare questo tipo di situazioni fino a digitare inferenza.