foldl è tail ricorsivo, quindi come mai foldr corre più veloce di foldl?

Volevo testare foldl vs foldr. Da quello che ho visto dovresti usare foldl over foldr quando puoi, grazie all’ottimizzazione della ricorsione di coda.

Questo ha senso. Tuttavia, dopo aver eseguito questo test, sono confuso:

foldr (richiede 0,057 s quando si usa il comando tempo):

a::a -> [a] -> [a] ax = ([x] ++ ) main = putStrLn(show ( sum (foldr a [] [0.. 100000]))) 

foldl (richiede 0.089 s quando si usa il comando time):

 b::[b] -> b -> [b] b xs = ( ++ xs). (\y->[y]) main = putStrLn(show ( sum (foldl b [] [0.. 100000]))) 

È chiaro che questo esempio è banale, ma sono confuso sul perché foldr stia battendo foldl. Non dovrebbe essere questo un caso in cui foldl vince?

Benvenuti nel mondo della valutazione pigra.

Quando ci pensi in termini di rigida valutazione, foldl sembra “buono” e foldr sembra “cattivo” perché foldl è codal ricorsivo, ma foldr dovrebbe build una torre nello stack in modo che possa elaborare prima l’ultimo object.

Tuttavia, la valutazione pigra trasforma le tabelle. Prendi, per esempio, la definizione della funzione mappa:

 map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = fx : map f xs 

Questo non sarebbe un granché se Haskell usasse una rigorosa valutazione, dal momento che avrebbe dovuto calcolare prima la coda, quindi anteporre l’object (per tutti gli elementi nella lista). L’unico modo per farlo in modo efficiente sarebbe build gli elementi al contrario, a quanto pare.

Tuttavia, grazie alla valutazione lenta di Haskell, questa funzione mappa è effettivamente efficiente. Gli elenchi in Haskell possono essere pensati come generatori e questa funzione mappa genera il primo elemento applicando f al primo elemento dell’elenco di input. Quando ha bisogno di un secondo object, fa di nuovo la stessa cosa (senza usare spazio extra).

Risulta che la map può essere descritta in termini di foldr :

 map f xs = foldr (\x ys -> fx : ys) [] xs 

È difficile da capire guardandolo, ma la valutazione pigra inizia perché foldr può dare subito il primo argomento:

 foldr fz [] = z foldr fz (x:xs) = fx (foldr fz xs) 

Poiché la f definita dalla map può restituire il primo elemento dell’elenco dei risultati utilizzando esclusivamente il primo parametro, la piega può operare pigramente in uno spazio costante.

Ora, la valutazione pigra fa mordere. Ad esempio, prova a eseguire sum [1..1000000]. Produce uno stack overflow. Perché dovrebbe? Dovrebbe solo valutare da sinistra a destra, giusto?

Diamo un’occhiata a come Haskell lo valuta:

 foldl fz [] = z foldl fz (x:xs) = foldl f (fzx) xs sum = foldl (+) 0 sum [1..1000000] = foldl (+) 0 [1..1000000] = foldl (+) ((+) 0 1) [2..1000000] = foldl (+) ((+) ((+) 0 1) 2) [3..1000000] = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000] ... = (+) ((+) ((+) (...) 999999) 1000000) 

Haskell è troppo pigro per eseguire le aggiunte man mano che procede. Invece, finisce con una torre di thunk non valorizzati che devono essere forzati per ottenere un numero. L’overflow dello stack si verifica durante questa valutazione, poiché è necessario ricorrere in profondità per valutare tutti i thunk.

Fortunatamente, esiste una funzione speciale in Data.List chiamata foldl' che opera rigorosamente. foldl' (+) 0 [1..1000000] non si sovrappone all’overflow. (Nota: ho provato a sostituire foldl con foldl' nel tuo test, ma in realtà l’ho rallentato.)

EDIT: esaminando nuovamente questo problema, penso che tutte le spiegazioni attuali siano abbastanza insufficienti, quindi ho scritto una spiegazione più lunga.

La differenza sta nel modo in cui foldl e foldl applicano la loro funzione di riduzione. Guardando il caso foldr , possiamo espandere come

 foldr (\x -> [x] ++ ) [] [0..10000] [0] ++ foldr a [] [1..10000] [0] ++ ([1] ++ foldr a [] [2..10000]) ... 

Questo elenco viene elaborato per sum , che lo consuma come segue:

 sum = foldl' (+) 0 foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000])) foldl' (+) 0 (0 : [1] ++ ... ++ [10000]) -- get head of list from '++' definition foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list foldl' (+) 0 (1 : [2] ++ ... ++ [10000]) foldl' (+) 1 ([2] ++ ... ++ [10000]) ... 

Ho omesso i dettagli della concatenazione della lista, ma è così che procede la riduzione. La parte importante è che tutto viene elaborato per minimizzare gli attraversamenti di liste. Il foldr attraversa solo una volta l’elenco, le concatenazioni non richiedono gli attraversamenti di elenchi continui e la sum fine consuma l’elenco in un unico passaggio. Criticamente, il capo della lista è disponibile da foldr immediatamente alla sum , quindi la sum può iniziare a lavorare immediatamente e i valori possono essere gc’d come vengono generati. Con le strutture di fusione come il vector , anche le liste intermedie saranno probabilmente fuse.

Contrasto con la funzione foldl :

 b xs = ( ++xs) . (\y->[y]) foldl b [] [0..10000] foldl b ( [0] ++ [] ) [1..10000] foldl b ( [1] ++ ([0] ++ []) ) [2..10000] foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000] ... 

Nota che ora il capo della lista non è disponibile fino a quando foldl ha finito. Ciò significa che l’intera lista deve essere costruita in memoria prima che la sum possa iniziare a funzionare. Questo è molto meno efficiente nel complesso. L’esecuzione delle due versioni con +RTS -s mostra prestazioni miserabili della raccolta dei dati obsoleti dalla versione foldl.

Questo è anche un caso in cui foldl' non aiuta. La rigidità aggiunta di foldl' non cambia il modo in cui viene creata la lista intermedia. Il capo della lista rimane non disponibile fino a quando foldl ‘non è finito, quindi il risultato sarà ancora più lento di foldr .

Io uso la seguente regola per determinare la migliore scelta di fold

  • Per le pieghe che sono una riduzione , usa foldl' (ad esempio questa sarà l’unica / finale traversata)
  • Altrimenti usa foldr .
  • Non usare foldl .

Nella maggior parte dei casi, foldr è la migliore funzione di piega poiché la direzione trasversale è ottimale per la valutazione lazy delle liste. È anche l’unico in grado di elaborare liste infinite. L’extra rigore di foldl' può renderlo più veloce in alcuni casi, ma dipende da come userete quella struttura e da quanto sia pigro.

Non credo che nessuno abbia mai detto la vera risposta su questo, a meno che non mi manchi qualcosa (che potrebbe essere vero e accolto con i downvotes).

Penso che il più grande in questo caso è che foldr costruisce la lista in questo modo:

[0] ++ ([1] ++ ([2] ++ (… ++ [1000000]))))

Mentre foldl costruisce la lista in questo modo:

((([0] ++ [1]) ++ [2]) ++ …) ++ [999888]) ++ [999999]) ++ [1000000]

La differenza è sottile, ma notate che nella versione foldr ++ ha sempre un solo elemento list come argomento sinistro. Con la versione foldl , ci sono fino a 999999 elementi nell’argomento sinistro di ++ (in media circa 500000), ma solo un elemento nell’argomento di destra.

Tuttavia, ++ richiede tempo proporzionale alla dimensione dell’argomento a sinistra, poiché deve guardare l’intero elenco di argomenti a sinistra fino alla fine e quindi reimpostare quell’ultimo elemento al primo elemento dell’argomento giusto (nella migliore delle ipotesi, forse in realtà ha bisogno di fare una copia). La lista degli argomenti giusti è invariata, quindi non importa quanto sia grande.

Ecco perché la versione foldl è molto più lenta. Secondo me non ha niente a che fare con la pigrizia.

Il problema è che l’ottimizzazione della ricorsione di coda è un’ottimizzazione della memoria, non un ottimizzazione del tempo di esecuzione!

L’ottimizzazione della ricorsione di coda evita la necessità di ricordare i valori per ogni chiamata ricorsiva.

Quindi, foldl è in effetti “buono” e foldr è “cattivo”.

Ad esempio, considerando le definizioni di foldr e foldl:

 foldl fz [] = z foldl fz (x:xs) = foldl f (z `f` x) xs foldr fz [] = z foldr fz (x:xs) = x `f` (foldr fz xs) 

Ecco come viene valutata l’espressione “foldl (+) 0 [1,2,3]”:

 foldl (+) 0 [1, 2, 3] foldl (+) (0+1) [2, 3] foldl (+) ((0+1)+2) [3] foldl (+) (((0+1)+2)+3) [ ] (((0+1)+2)+3) ((1+2)+3) (3+3) 6 

Nota che foldl non ricorda i valori 0, 1, 2 …, ma passa l’intera espressione (((0 + 1) +2) +3) come argomento pigramente e non lo valuta fino all’ultima valutazione di foldl, dove raggiunge il caso base e restituisce il valore passato come secondo parametro (z) che non è ancora stato valutato.

D’altra parte, è così che foldr funziona:

 foldr (+) 0 [1, 2, 3] 1 + (foldr (+) 0 [2, 3]) 1 + (2 + (foldr (+) 0 [3])) 1 + (2 + (3 + (foldr (+) 0 []))) 1 + (2 + (3 + 0))) 1 + (2 + 3) 1 + 5 6 

La differenza importante qui è che dove foldl valuta l’intera espressione nell’ultima chiamata, evitando il bisogno di tornare a raggiungere i valori memorizzati, foldr no. foldr ricorda un numero intero per ogni chiamata ed esegue un’aggiunta in ogni chiamata.

È importante ricordare che foldr e foldl non sono sempre equivalenti. Ad esempio, prova a calcolare queste espressioni negli abbracci:

 foldr (&&) True (False:(repeat True)) foldl (&&) True (False:(repeat True)) 

foldr e foldl sono equivalenti solo in determinate condizioni qui descritte

(scusa per il mio cattivo inglese)

Per a, l’elenco [0.. 100000] deve essere espanso immediatamente in modo che foldr possa iniziare con l’ultimo elemento. Quindi, mentre unisce le cose insieme, i risultati intermedi sono

 [100000] [99999, 100000] [99998, 99999, 100000] ... [0.. 100000] -- ie, the original list 

Poiché nessuno è autorizzato a modificare questo valore di lista (Haskell è un puro linguaggio funzionale), il compilatore è libero di riutilizzare il valore. I valori intermedi, come [99999, 100000] possono anche essere semplicemente dei puntatori nell’elenco [0.. 100000] espanso anziché in elenchi separati.

Per b, guarda i valori intermedi:

 [0] [0, 1] [0, 1, 2] ... [0, 1, ..., 99999] [0.. 100000] 

Ciascuno di questi elenchi intermedi non può essere riutilizzato, perché se si modifica la fine dell’elenco, si sono modificati tutti gli altri valori che puntano ad esso. Quindi stai creando una serie di elenchi aggiuntivi che richiedono tempo per creare memoria. Quindi in questo caso dedichiamo molto più tempo ad allocare e compilare questi elenchi che sono valori intermedi.

Dato che stai solo facendo una copia dell’elenco, una corsa è più veloce perché inizia espandendo l’elenco completo e poi continua a spostare un puntatore dal retro della lista in primo piano.

foldlfoldl sono ottimizzati per la coda. È solo foldl' .

Ma nel tuo caso l’uso di ++ con foldl' non è una buona idea, perché la successiva valutazione di ++ causerà l’accumularsi dell’accumulatore sempre più volte.

Bene, permettimi di riscrivere le tue funzioni in un modo che la differenza dovrebbe essere ovvia –

 a :: a -> [a] -> [a] a = (:) b :: [b] -> b -> [b] b = flip (:) 

Vedi che b è più complesso di a. Se si desidera essere precisi, è necessario calcolare un passo di riduzione per calcolare il valore, ma b bisogno due. Questo fa sì che la differenza di tempo che stai misurando, nel secondo esempio il doppio delle riduzioni devono essere eseguite.

// edit: Ma la complessità temporale è la stessa, quindi non mi preoccuperei molto di ciò.