È possibile ottimizzare il caso presentato in un ciclo?

Question

Supponiamo che abbia due funzioni f :: [a] -> b e g :: [a] -> c. Ho le seguenti due domande:

1. Se effettuo (f &&& g) xs dove xs :: [a], e se entrambi f e g coinvolgono loop, è possibile per il compilatore per ottimizzare questi due loop in uno? (Si prega di notare che non sto chiedendo se alcuni specifici compilatore Haskell implementa questa. Voglio sapere se una cosa del genere è possibile.)

2. Può la funzione traverse da Traverse tipo di aiuto di classe mi hanno una tale ottimizzazione con qualcosa lungo le seguenti linee:

   traverse (someCombinator f g) xs 
   

Answer 1

è teoricamente possibile ottimizzare questo codice, ma molto molto difficile, perché f e g potrebbe consumare diverse quantità di lista di input. Solo quando consumano lo stesso importo o g consuma sempre più della lista rispetto a f (o viceversa), sarebbe possibile eseguire l'ottimizzazione. Il problema di interruzione impedisce a un compilatore di rilevare tali condizioni in un codice complesso.

Solo in casi semplici, dove sia sia g utilizzano foldr internamente, ad esempio, sarebbe possibile eseguire ottimizzazioni banali senza ulteriore introspezione.

La funzione traverse non vi aiuterà qui, perché non esiste un modo ragionevole di attuazione someCombinator (Come si desidera trasformare più chiamate di a 's in uno [a] senza hack gravi? E poi sono tornati al punto di partenza in ogni modo).

L'unica opzione reale è di rendere f e g in cartelle, in modo che abbiano le firme f :: a -> b -> b e g :: a -> c -> c, il che significa che il valore di b e c può essere calcolato in modo incrementale. È quindi possibile utilizzare \ a -> f a *** g a per ottenere una cartella che è possibile utilizzare in una piegatura convenzionale (a destra, in questo caso).