Perché foldr utilizza una funzione di supporto?

Question

Nello spiegare foldr a Haskell neofiti, la definizione canonica è

foldr   :: (a -> b -> b) -> b -> [a] -> b 
foldr _ z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

Ma in GHC.Base, foldr è definito come

foldr k z = go 
      where 
      go []  = z 
      go (y:ys) = y `k` go ys 

Sembra che questa definizione è un'ottimizzazione per la velocità, ma io don capisco perché usare la funzione helper go lo renderebbe più veloce. I commenti alla fonte (see here) menzionano l'inlining, ma non vedo anche come questa definizione migliorerebbe l'inlining.

Answer 1

Posso aggiungere alcuni dettagli importanti sul sistema di ottimizzazione di GHC.

La definizione ingenua di foldr passa attorno a una funzione. C'è un sovraccarico inerente nel chiamare una funzione, specialmente quando la funzione non è nota al momento della compilazione. Sarebbe davvero bello poter allineare la definizione della funzione se è nota al momento della compilazione.

Ci sono trucchi disponibili per eseguire tale inlining in GHC - e questo è un esempio di questi. Innanzitutto, è necessario inserire foldr (verrà spiegato il motivo dopo). L'implementazione ingenua di foldr è ricorsiva, quindi non può essere sottolineata. Quindi una trasformazione worker/wrapper viene applicata alla definizione. Il lavoratore è ricorsivo, ma il wrapper non lo è. Ciò consente di allineare foldr, nonostante la ricorsione sulla struttura dell'elenco.

Quando foldr è in linea, crea anche una copia di tutti i collegamenti locali. È più o meno un inlining testuale diretto (modulo alcuni rinominare, e succede dopo il passaggio di desugaring). Questo è dove le cose si fanno interessanti. go è un'associazione locale e l'ottimizzatore deve cercare al suo interno. Si accorge che chiama una funzione nell'ambito locale, che chiama k. GHC rimuoverà spesso la variabile k interamente e la sostituirà semplicemente con l'espressione k ridotta a. E poi in seguito, se l'applicazione della funzione è suscettibile di inlining, può essere inline in questo momento - rimuovendo il sovraccarico di chiamare completamente una funzione di prima classe.

Diamo un'occhiata a un esempio semplice e concreto. Questo programma eco di una linea di ingresso con tutti i finali 'x' caratteri rimossi:

dropR :: Char -> String -> String 
dropR x r = if x == 'x' && null r then "" else x : r 

main :: IO() 
main = do 
    s <- getLine 
    putStrLn $ foldr dropR "" s 

Innanzitutto, l'ottimizzatore inline foldr s' definizioni e semplificare, con conseguente codice che assomigli a questo:

main :: IO() 
main = do 
    s <- getLine 
    -- I'm changing the where clause to a let expression for the sake of readability 
    putStrLn $ let { go [] = ""; go (x:xs) = dropR x (go xs) } in go s 

E questa è la cosa che consente la trasformazione worker-wrapper .. Salterò i passaggi rimanenti, ma dovrebbe essere ovvio che GHC può ora incorporare la definizione di dropR, eliminando l'overhead di chiamata della funzione. È qui che arriva la grande vittoria per le prestazioni.

Answer 2

come i commenti dicono:

-- Inline only in the final stage, after the foldr/cons rule has had a chance 
-- Also note that we inline it when it has *two* parameters, which are the 
-- ones we are keen about specialising! 

In particolare, si noti il ​​"noi inline quando ha due parametri, che sono quelli che sei appassionato di specializzazione!"

Ciò sta dicendo è che quando foldr ottiene inline, si sta facendo inline solo per la scelta specifica di f e z, non per la scelta della lista sempre piegato. Io non sono un esperto, ma sembrerebbe che renderebbe possibile inline in situazioni come

map (foldr (+) 0) some_list 

in modo che la linea accade in questa linea e non dopo map è stato applicato. Ciò lo rende ottimizzabile in più situazioni e più facilmente. Tutta la funzione di aiuto fa mascherare il terzo argomento in modo che {-# INLINE #-} possa fare la sua cosa.

Answer 3

GHC non può inline funzioni ricorsive, così

foldr   :: (a -> b -> b) -> b -> [a] -> b 
foldr _ z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

non può essere inline. Ma

foldr k z = go 
     where 
     go []  = z 
     go (y:ys) = y `k` go ys 

non è una funzione ricorsiva. È una funzione non ricorsiva con una definizione ricorsiva locale!

Ciò significa che, come @bheklilr scrive, in map (foldr (+) 0) il foldr può essere inline e quindi f e z sostituito da (+) e 0 nel nuovo go, e grandi cose possono accadere, come unboxing del valore intermedio.

Answer 4

Un piccolo dettaglio importante non menzionato in altre risposte è che GHC, data una definizione di funzione come

f x y z w q = ... 

non può inline f finché tutti gli argomenti x, y, sono applicati z, w e q. Ciò significa che è spesso vantaggioso utilizzare la trasformazione worker/wrapper per esporre un set minimo di argomenti di funzione che devono essere applicati prima che si possa verificare l'inlining.