Wie Sie wissen, wann verwenden Klapp links und wenn Falte rechts benutzen?

Question

Ich bin mir bewusst, dass Falte links linksgerichtete Bäume produziert und zerlegbare rechts erzeugt rechtsgerichtete Bäume, aber wenn ich für eine Falte zu erreichen, ich mich manchmal finden in verzetteln Kopfschmerzen auslösende Gedanke versucht, zu bestimmen, welche Art Falte angemessen ist. Ich am Ende in der Regel das gesamte Problem Abwickeln und durch die Umsetzung der Falzfunktion Schritt wie es mein Problem gilt.

Also, was ich wissen will, ist:

• Was sind einige Faustregeln zu bestimmen, ob links zu falten oder rechts falten?
• Wie kann ich schnell, welche Art von Falte entscheiden, das Problem gegeben verwende ich bin vor?

Es gibt ein Beispiel in Scala von Beispiel (PDF) von eine Falte mit einer Funktion namens Flatten zu schreiben, die eine Liste von Elementlisten in eine einzige Liste verkettet. In diesem Fall ist eine richtige Falte die richtige Wahl (angesichts die Art und Weise der Listen verkettet), aber ich hatte darüber nachzudenken etwas zu diesem Ergebnis zu gelangen.

Da Faltung ist eine solche gemeinsame Aktion in (funktionale) Programmierung, ich möchte in der Lage sein, diese Art von Entscheidungen zu treffen, schnell und sicher. So ... irgendwelche Tipps?

Answer 1

Sie können eine Falte in eine Infixoperator Notation übertragen (Schreiben dazwischen):

Dieses Beispiel klappen Sie die Akkufunktion x mit

fold x [A, B, C, D]

ist somit gleich

A x B x C x D

Jetzt müssen Sie nur noch über die Assoziativität des Betreibers Vernunft (in Klammern setzen!).

Wenn Sie eine Linksassoziativität Operator, werden Sie die Klammern wie folgt festgelegt

((A x B) x C) x D

Hier können Sie verwenden, um eine links falten . Beispiel (Haskell-Stil Pseudo-Code)

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

Wenn Ihr Operator ist rechtsassoziativ ( rechts falten ), würden die Klammern wie folgt eingestellt werden:

A x (B x (C x D))

Beispiel: Cons-Operator

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

Im allgemeinen arithmetischen Operatoren (die meisten Operatoren) sind linksassoziativ, so foldl ist weiter verbreitet. Aber in den anderen Fällen Infixschreibweise + Klammern ist sehr nützlich.

Answer 2

Olin Shivers differenziert sie mit den Worten „foldl das ist grundlegende Liste Iterator“und‚foldr ist die grundlegende Liste Rekursion Betreiber.‘ Wenn Sie schauen, wie foldl Werke:

((1 + 2) + 3) + 4

Sie können den Speicher sehen (wie in einer Schwanz-rekursive Iteration) gebaut. Im Gegensatz dazu foldr Erlös:

1 + (2 + (3 + 4))

, wo Sie die Traversal zum Basisfall 4 sehen können und das Ergebnis von dort aufzubauen.

Also ich postulieren eine Daumenregel:., Wenn es sich wie eine Liste Iteration sieht, eine, die einfach sein würde, in tail-rekursive Form zu schreiben, foldl ist der Weg zu gehen

Aber wirklich wird dies wahrscheinlich sein am deutlichsten aus der Assoziativität der Operatoren Sie verwenden. Wenn sie links-assoziativ sind, verwenden Sie foldl. Wenn sie richtig assoziativ sind, verwenden foldr.

Answer 3

Andere Plakate haben gute Antworten gegeben und ich werde nicht wiederholen, was sie schon gesagt haben. Wie Sie ein Scala Beispiel in der Frage gegeben habe, werde ich ein Scala konkretes Beispiel. Wie Tricks schon gesagt, ein foldRight n-1 Stack-Frames erhalten muss, wo n die Länge der Liste ist, und dies kann leicht führen zu einem Stapelüberlauf - und nicht einmal Endrekursion könnten Sie von diesem speichern.

Ein List(1,2,3).foldRight(0)(_ + _) reduzieren würde an:

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)

während List(1,2,3).foldLeft(0)(_ + _) reduzieren würde zu:

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

, die iterativ berechnet werden kann, wie in der Implementierung von List .

In einer streng ausgewerteten Sprache wie Scala, ein foldRight kann den Stack für große Listen leicht bläst, während ein foldLeft nicht.

Beispiel:

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...

Faust Meine Regel ist daher - für die Betreiber, die zumindest in Scala keine spezifische Assoziativität haben, immer foldLeft verwenden. Andernfalls gehen Sie mit anderen Ratschläge in den Antworten gegeben;).

Answer 4

Es ist auch erwähnenswert, (und ich weiß, das ist die offensichtliche ein Bit Angabe), im Falle eines kommutativen Bediener die beiden ziemlich gleichwertig sind. In dieser Situation ein foldl könnte die bessere Wahl sein:

foldl: (((1 + 2) + 3) + 4) kann jede Operation berechnen und trägt den akkumulierten Wert nach vorn

foldr: (1 + (2 + (3 + 4))) braucht einen Stapelrahmen für 1 + ? und 2 + ? geöffnet werden, bevor 3 + 4 Berechnung, dann muss es um die Berechnung für jeden zurückgehen und tun.

Ich bin nicht genug von einem Experten für funktionale Sprachen oder Compiler-Optimierungen zu sagen, ob dies tatsächlich einen Unterschied machen, aber es scheint sicher, sauberer einen foldl mit kommutativen Operatoren zu verwenden.