まず、私が読んでいるReal World Haskellfoldlは、決して使用せず、代わりに使用するように言っていますfoldl'。だから信頼している。
しかし、私はいつfoldr対を使うべきかについてぼんやりしていますfoldl'。目の前に並べられた仕組みの違いはわかるのですが、「どっちがいい」と理解できないほどバカです。両方とも同じ答えを生成するため、どちらを使用しても問題ないように思われると思います (そうではありませんか?)。実際、この構造に関する私の以前の経験は、Rubyinjectと Clojure のreduceもので、「左」と「右」のバージョンがないようです。(補足質問: どのバージョンを使用していますか?)
私のようなスマートに挑戦するソートを助けることができる洞察は大歓迎です!
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全体を調べる必要がないことです。例えばxfoldr
foldr (&&) False (repeat False)
一方False、
foldl (&&) False (repeat False)
終了することはありません。(注:repeat Falseすべての要素が である無限リストを作成しますFalse。)
一方、foldl'は末尾再帰的で厳密です。何があってもリスト全体をトラバースする必要があることがわかっている場合 (たとえば、リスト内の数値を合計するなど)、foldl'よりも空間 (およびおそらく時間) 効率が高くなりfoldrます。
foldlそれらのセマンティクスは異なるため、とを交換することはできませんfoldr。1 つは要素を左から、もう 1 つは右から要素を折り畳みます。このようにして、演算子は異なる順序で適用されます。これは、減算などのすべての非関連操作に関係します。
Haskell.orgには、このテーマに関する興味深い記事があります。
簡単に言うfoldrと、アキュムレータ関数が 2 番目の引数で遅延している場合の方が優れています。詳細については、Haskell wiki のスタック オーバーフロー(しゃれを意図したもの) を参照してください。
foldl'すべての用途の 99% で好まれる理由はfoldl、ほとんどの用途で一定のスペースで実行できるためです。
関数を取るsum = foldl['] (+) 0。を使用するfoldl'と、合計がすぐに計算されるためsum、無限リストへの適用は永久に実行され、ほとんどの場合、一定のスペースで実行されます ( Ints、Doubles、FloatsなどIntegerを使用している場合)。数より大きくなりmaxBound :: Intます）。
を使用foldlすると、サンクが構築されます (回答を保存するのではなく、後で評価できる、回答を取得する方法のレシピのように)。これらのサンクは多くのスペースを占有する可能性があり、この場合、サンクを格納するよりも式を評価する方がはるかに優れています (スタック オーバーフローにつながります...そして、気にしないでください)。
それが役立つことを願っています。
ちなみに、Rubyinjectと Clojurereduceはfoldl(またはfoldl1、使用するバージョンによっては ) です。通常、言語にフォームが 1 つしかない場合、それは Python reduce、Perl List::Util::reduce、C++ accumulate、C# Aggregate、Smalltalk inject:into:、PHP array_reduce、MathematicaFoldなどを含む左折です。Common Lisp のreduceデフォルトは左折ですが、右折のオプションがあります。
Konradが指摘するように、それらのセマンティクスは異なります。それらは同じタイプさえ持っていません：
ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci>
たとえば、リスト追加演算子 (++) は次のように実装できますfoldr。
(++) = flip (foldr (:))
その間
(++) = flip (foldl (:))
タイプエラーになります。