[解決済み] fold-leftを使うタイミングとfold-rightを使うタイミングはどのように見極めるのですか？

質問

fold-leftが左向きの木を生成し、fold-rightが右向きの木を生成することは知っていますが、foldに手を伸ばすと、どの種類のfoldが適切かを判断しようとすると、頭痛がするほど考え込んでしまうことがあります。 私は通常、問題全体を解きほぐし、自分の問題に適用されるfold関数の実装を段階的に進めていくことにしています。

そこで、私が知りたいのは

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

に例があります。 例によるScala (PDF) に、要素リストのリストを一つのリストに連結する flatten という関数を書くために fold を使う例があります。 その場合、(リストが連結される方法を考えると) 右の fold が適切な選択ですが、その結論に達するには少し考える必要がありました。

折りたたみは（関数型）プログラミングでは非常に一般的な動作なので、私はこの種の決定を素早く自信を持って行えるようになりたいと思っています。 それで...何かヒントはありますか？

どのように解決するのですか？

foldをinfix演算子表記に変換する（間に書き込む）ことができます。

この例のfoldは、アキュムレータ関数 x

fold x [A, B, C, D]

というように

A x B x C x D

あとは演算子の連想性を推論するだけです（括弧をつけることで！）。

もしあなたが 左結合性 演算子を使うと、次のように括弧を設定することになります。

((A x B) x C) x D

ここでは 左折り . 例（ハッシュ関数風の擬似コード）

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 の方が普及しています。しかし、それ以外の場合は、infix記法＋括弧がかなり有効です。