[解決済み] foldrとfoldl（またはfoldl'）の意味するところ

質問

まず最初に。 リアルワールドハスケル を使うなと書いてあります。 foldl を使用し、代わりに foldl' . だから信用しています。

しかし、どのような場合に使うのか、もやもやしています。 foldr vs. foldl' . 目の前に両者の動作が異なる構造が並べられているのはわかるのですが、私は頭が悪いので、いつ"どちらが良いのか理解できていません。実際、私がこの構文に出会ったのは、Rubyの inject とClojureの reduce には、quot;left" と "right" のバージョンはないようです。(横の質問: 彼らはどのバージョンを使っているのでしょうか?)

私のような頭でっかちな人間を助けてくれるような洞察があれば、とてもありがたいです。

解決方法は？

の再帰は foldr f x ys ここで ys = [y1,y2,...,yk] のように見えます。

f y1 (f y2 (... (f yk x) ...))

に対する再帰は foldl f x ys は次のようになります。

f (... (f (f x y1) y2) ...) yk

ここでの重要な相違点は、もし f x y の値だけを使って計算することができます。 x であれば foldr はリスト全体を検査する必要はありません。例えば

foldr (&&) False (repeat False)

リターン False 一方

foldl (&&) False (repeat False)

が終了することはありません。(注 repeat False は無限リストを作成し、すべての要素が False .)

一方 foldl' は末尾再帰的で厳密です。何があってもリスト全体を走査しなければならないことが分かっている場合（例えば、リスト内の数字の合計など）には foldl' の方が、よりスペース（とおそらく時間）効率が良い。 foldr .