左折を使用するタイミングと右折を使用するタイミングをどのように知っていますか？

StackOverflow https://stackoverflow.com/questions/1446419

質問

fold-leftは左に傾いた木を生成し、fold-rightは右に傾いた木を生成することを知っていますが、折り目に手を伸ばすと、ときどき頭痛を誘発する思考で行き詰まってしまいます。折り目の種類が適切です。私は通常、問題全体を解き、問題に当てはまるようにfold関数の実装をステップスルーします。

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

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

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

折りたたみは（関数型）プログラミングで非常に一般的なアクションであるため、この種の決定を迅速かつ自信を持って行えるようにしたいと思います。それで...ヒントはありますか？

役に立ちましたか？

解決

折り畳みを中置演算子表記に変換できます（間に書き込む）：

この例は、アキュムレーター関数 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))

例：Cons-Operator 

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

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

他のヒント

Olin Shivers は、＆quot; foldlは基本的なリスト反復子＆quot; ＆fold;は基本的なリスト再帰演算子です。＆quot; foldlの仕組みを見ると：

((1 + 2) + 3) + 4

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

1 + (2 + (3 + 4))

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

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

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

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

A List（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)

while List（1,2,3）.foldLeft（0）（_ + _）は次のようになります：

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

List の実装。

Scalaとして厳密に評価された言語では、 foldRight は大きなリストのスタックを簡単に爆破できますが、 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...
したがって、私の経験則では、特定の結合性を持たない演算子については、少なくともScalaでは常に foldLeft を使用します。それ以外の場合は、回答に記載されている他のアドバイスに従ってください;）。

注意する価値もあります（そして、これは明らかなことを少し述べていることを理解しています）。可換演算子の場合、この2つはほとんど同等です。この状況では、foldlの方が適切な場合があります。

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

folder： （1 +（2 +（3 + 4）））は、前に 1 +？および 2 +？のスタックフレームを開く必要があります 3 + 4 を計算したら、戻ってそれぞれの計算を行う必要があります。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top