Come fai a sapere quando usare piega a sinistra e quando usare piega a destra?

Question

Sono consapevole che piega a sinistra produce alberi inclinati a sinistra e piega a destra produce alberi inclinati a destra, ma quando raggiungo una piega, a volte mi ritrovo a impantanarmi in pensieri che inducono mal di testa cercando di determinare quale il tipo di piega è appropriato. Di solito finisco per svelare l'intero problema e passare attraverso l'implementazione della funzione di piega in quanto si applica al mio problema.

Quindi quello che voglio sapere è:

• Quali sono alcune regole pratiche per determinare se piegare a sinistra o piegare a destra?
• Come posso decidere rapidamente quale tipo di piega utilizzare in considerazione del problema che sto affrontando?

C'è un esempio in Scala per esempio (PDF) di usando una piega per scrivere una funzione chiamata appiattisci che concatena un elenco di elenchi di elementi in un unico elenco. In quel caso, una piega a destra è la scelta giusta (dato il modo in cui le liste sono concatenate), ma ho dovuto pensarci un po 'per arrivare a quella conclusione.

Poiché il fold è un'azione così comune nella programmazione (funzionale), mi piacerebbe poter prendere questo tipo di decisioni in modo rapido e sicuro. Quindi ... qualche consiglio?

Answer 1

Puoi trasferire una piega in una notazione dell'operatore infix (scrivendo tra):

Questo esempio piega usando la funzione di accumulatore x

fold x [A, B, C, D]

quindi uguale a

A x B x C x D

Ora devi solo ragionare sull'associatività del tuo operatore (mettendo le parentesi!)

Se hai un operatore associativo di sinistra , imposterai le parentesi in questo modo

((A x B) x C) x D

Qui, usi una piega a sinistra . Esempio (pseudocodice in stile haskell)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

Se il tuo operatore è associativo a destra ( piega a destra ), le parentesi verrebbero impostate in questo modo:

A x (B x (C x D))

Esempio: contro-operatore

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

In generale, gli operatori aritmetici (la maggior parte degli operatori) sono associativi di sinistra, quindi foldl è più diffuso. Ma negli altri casi, notazione infisso + parentesi è abbastanza utile.

Answer 2

Olin Shivers li ha differenziati dicendo " foldl is l'iteratore dell'elenco fondamentale " e "foldr è l'operatore di ricorsione dell'elenco fondamentale." Se osservi come funziona foldl:

((1 + 2) + 3) + 4

puoi vedere l'accumulatore (come in un'iterazione ricorsiva della coda) in costruzione. Al contrario, foldr procede:

1 + (2 + (3 + 4))

dove puoi vedere l'attraversamento al caso base 4 e costruire il risultato da lì.

Quindi sostengo una regola empirica: se sembra una ripetizione dell'elenco, che sarebbe semplice scrivere in forma ricorsiva alla coda, foldl è la strada da percorrere.

Ma davvero questo sarà probabilmente più evidente dall'associatività degli operatori che stai usando. Se sono associativi di sinistra, utilizzare foldl. Se sono associati a destra, utilizzare foldr.

Answer 3

Altri poster hanno dato buone risposte e non ripeterò quello che hanno già detto. Dato che hai fornito un esempio di Scala nella tua domanda, darò un esempio specifico di Scala. Come Trucchi ha già detto, un foldRight deve conservare n-1 frame stack, dove n è la lunghezza del tuo elenco e questo può facilmente portare a un overflow dello stack - e nemmeno la ricorsione della coda potrebbe salvarti da questo.

Un List (1,2,3) .foldRight (0) (_ + _) si ridurrebbe a:

1 + List(2,3).foldRight(0)(_ + _)        // first stack frame
    2 + List(3).foldRight(0)(_ + _)      // second stack frame
        3 + 0                            // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well)

mentre List (1,2,3) .foldLeft (0) (_ + _) si riduce a:

(((0 + 1) + 2) + 3)

che può essere calcolato iterativamente, come nel implementazione di List .

In un linguaggio rigorosamente valutato come Scala, un foldRight può facilmente far esplodere lo stack per elenchi di grandi dimensioni, mentre un foldLeft non lo farà.

Esempio:

scala> List.range(1, 10000).foldLeft(0)(_ + _)
res1: Int = 49995000

scala> List.range(1, 10000).foldRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...

La mia regola empirica è quindi - per gli operatori che non hanno una associatività specifica, utilizzare sempre foldLeft , almeno in Scala. Altrimenti, segui altri consigli forniti nelle risposte;).

Answer 4

Vale anche la pena notare (e mi rendo conto che questo è un po 'ovvio), nel caso di un operatore commutativo i due sono praticamente equivalenti. In questa situazione, un foldl potrebbe essere la scelta migliore:

foldl: (((1 + 2) + 3) + 4) può calcolare ogni operazione e portare avanti il ??valore accumulato

foldr: (1 + (2 + (3 + 4))) richiede l'apertura di un frame dello stack per 1 +? e 2 +? prima calcolando 3 + 4 , quindi deve tornare indietro ed eseguire il calcolo per ciascuno.

Non sono abbastanza esperto di linguaggi funzionali o ottimizzazioni del compilatore per dire se questo farà effettivamente la differenza, ma sicuramente sembra più pulito usare una piega con operatori commutativi.