まず、リアルワールドHaskell私が読んでいる には、決して を使用せずfoldl、代わりに を使用するようにと書かれていますfoldl'。だから私はそれを信頼しています。
foldrしかし、と をいつ使用すfoldl'べきかはよくわかりません。 それらがどのように異なる動作をするかの構造は目の前に示されていても、私は「どちらが優れているか」を理解するにはあまりにも愚かです。 どちらが使用されてもあまり問題ではないように思われます。 どちらも同じ答えを生成するからです (そうではありませんか?)。 実際、この構造に関する私の以前の経験は、Ruby のinjectと Clojure のからのものでありreduce、これらには「左」バージョンと「右」バージョンがないようです。 (余談ですが、どちらのバージョンが使用されているのでしょうか?)
私のような頭の悪い人間にとって役立つ洞察があれば、ぜひ教えてください。
ベストアンサー1
foldr f x yswhereの再帰は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。