106

左に折りたたむと左寄りの木ができ、右に折りたたむと右寄りの木ができることは知っていますが、折り目に手を伸ばすと、頭痛を誘発する思考にとらわれて、どの種類の折り目を判断しようとすることがあります。適切です。私は通常、問題全体を巻き戻し、問題に適用されるfold関数の実装を段階的に実行することになります。

だから私が知りたいのは：

  • 左に折りたたむか右に折りたたむかを決定するための経験則は何ですか？
  • 私が直面している問題を考慮して、どのタイプの折り目を使用するかをすばやく決定するにはどうすればよいですか？

Scala by Example（PDF）には、foldを使用して、要素リストのリストを1つのリストに連結するflattenという関数を作成する例があります。その場合、（リストを連結する方法を考えると）正しい折り畳みが適切な選択ですが、その結論に到達するために少し考えなければなりませんでした。

フォールディングは（関数型）プログラミングでは非常に一般的なアクションなので、このような決定を迅速かつ自信を持って行えるようにしたいと思います。だから...何かヒントはありますか？

4

4 に答える 4

114

折り畳みを中置演算子表記（間に書き込む）に転送できます。

この例は、アキュムレータ関数を使用して折りたたむx

fold x [A, B, C, D]

したがって、

A x B x C x D

ここで、演算子の結合性について推論する必要があります（括弧を付けることによって！）。

左結合演算子がある場合は、このように括弧を設定します

((A x B) x C) x D

ここでは、左折りを使用します。例（haskellスタイルの擬似コード）

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

演算子が右結合（右折り）の場合、括弧は次のように設定されます。

A x (B x (C x D))

例：短所-オペレーター

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

一般に、算術演算子（ほとんどの演算子）は左結合であるため、foldlより広く使用されています。しかし、他の場合には、中置記法+括弧は非常に便利です。

于 2009-09-18T19:40:11.747 に答える
66

Olin Shiversは、「foldlは基本的なリストの反復子である」、「foldrは基本的なリストの再帰演算子である」と言ってそれらを区別しました。foldlがどのように機能するかを見ると：

((1 + 2) + 3) + 4

アキュムレータが（末尾再帰の反復のように）構築されているのを見ることができます。対照的に、foldrは次のように進行します。

1 + (2 + (3 + 4))

ここで、ベースケース4へのトラバーサルと、そこからの結果の構築を確認できます。

だから私は経験則を仮定します：それがリストの反復のように見えるなら、それは末尾再帰形式で書くのが簡単でしょう、foldlは行く方法です。

しかし実際には、これはおそらく、使用している演算子の結合性から最も明白になります。それらが左結合である場合は、foldlを使用します。それらが右結合である場合は、foldrを使用します。

于 2009-09-18T20:55:27.493 に答える
29

他のポスターは良い答えを出しました、そして私は彼らがすでに言ったことを繰り返しません。質問でScalaの例を挙げたので、Scala固有の例を示します。Tricksがすでに述べたように、スタックフレームを保持する必要がfoldRightあります。これはリストの長さであり、これはスタックオーバーフローにつながる可能性があります。末尾再帰でさえ、これからあなたを救うことはできません。n-1n

AList(1,2,3).foldRight(0)(_ + _)は次のようになります。

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)

にList(1,2,3).foldLeft(0)(_ + _)減少しますが：

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

これは、の実装でList行われるように、繰り返し計算できます。

Scalaとして厳密に評価された言語では、afoldRightは大きなリストのスタックを簡単に爆破できますが、そうでfoldLeftはありません。

例：

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

したがって、私の経験則は、特定の結合性を持たない演算子の場合foldLeft、少なくともScalaでは常にを使用することです。それ以外の場合は、回答に記載されている他のアドバイスを参考にしてください;）。

于 2009-09-19T21:10:58.627 に答える
4

また、注目に値します（そして、これは明らかなことを少し述べていることを私は理解しています）。可換演算子の場合、2つはほとんど同等です。この状況では、foldlがより良い選択かもしれません：

foldl： (((1 + 2) + 3) + 4)各操作を計算し、累積値を繰り越すことができます

foldr： 計算する前に(1 + (2 + (3 + 4)))スタックフレームを開く必要があります1 + ?。その後、戻ってそれぞれの計算を行う必要があります。2 + ?3 + 4

関数型言語やコンパイラの最適化の専門家では、これが実際に違いを生むかどうかを判断するのに十分ではありませんが、可換演算子でfoldlを使用する方が確かにクリーンなようです。

于 2009-09-18T20:20:05.957 に答える