foldlの観点からfoldrを再定義（実装）できないのはなぜですか

Question

これはfoldl can be implemented in terms of foldrです。これは、A tutorial on the universality and expressiveness of foldで詳細に説明されています。これとは対照的に

は、原因foldlは、そのリストの引数の末尾に厳しいですが、foldではないという事実に、foldlの面でfoldを再定義することはできません。論文では、と述べられています。

私は（元の紙foldにfoldrの同義語であることに注意）これはfoldlの面でfoldrを定義することが不可能に証拠を構成する方法を確認するために失敗するが。私は厳密さがここでどのように役割を果たすかを理解しようとすると非常に困惑しています。誰かがこの説明を展開できますか？

Answer 1

をfoldrとします（これはHaskell標準ライブラリで呼ばれているためです）。リストはWNHFに評価され、他の全てのケースで、我々はすぐに再帰 - ベースケースは[]するlist引数が必要であることを

---

撮影foldlの定義をもう一度見て、

foldl :: (β -> α -> β) -> β -> [α] -> β 
foldl f v [] = v 
foldl f v (x:xs) = foldl f (f v x) xs 

ノートリストの末尾を使用します。それはfoldlがその（最後の）リスト引数に厳密であるという事実を確立する。

を使用してfoldrのバージョンを書きますが、有限の長さのリストでのみ機能します。モチベーションについては、this pageを参照してください。

foldr' :: (α -> β -> β) -> β -> [α] -> β 
foldr' f v xs = foldl (\g u x -> g (f u x)) id xs v 

問題を表示するには、のは右の倍を使用して合計でheadのバージョンを記述してみましょう。

import Control.Applicative ((<|>)) 

safeHead :: [α] -> Maybe α 
safeHead = foldr (\x y -> Just x <|> y) Nothing 

我々はfoldr'をベース当社foldlでfoldrを交換する場合、我々はもはや無限リストsafeHead [1..]の頭を見つけることができます。 safeHeadがリストの最初の要素だけを調べる必要があるとしても、基礎となるfoldlは無限リスト全体を走査しようとします。

---

プレリュードに存在する実際既に、それはリストが空でない場合、foldrに再帰呼び出しが内部あることlistToMaybe

Answer 2

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f acc [] = acc 
foldr f acc (x : xs) = f x (foldr f acc xs) 

ノートと呼ばれるこのような関数引数がfに渡されました。 Haskellは遅延評価されているので、foldrへの再帰呼び出しは必ずしも実際には計算されません。fは、第二引数を調べずに結果を返すことができます（ただしがxには、それが2番目の引数を見たいかどうかをを決める最初の引数を調べることができる）場合は、foldrコールは「早期に停止」することができ、なしリスト全体を調べる。ここで、（リストが空でない場合）foldl再帰直ちに、それは再帰呼び出しに渡さアキュムレータ引数内部fへの呼び出しと

foldl :: (b -> a -> b) -> b -> [a] -> b 
foldl f acc [] = acc 
foldl f acc (x : xs) = foldl (f acc x) xs 

。 fは、再帰呼び出しを調べるかどうかを決定する機会を得ません。 foldlは、再帰を維持する期間を完全に制御しており、リストの終わりを見つけるまで続行します。

特に、foldrを使用すると、無限のリストを処理する可能性があります。最終的に渡す関数が第2引数（acc）を参照しない限りGHCiの中にたとえば：

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..5] 
"1, 2, 3, 4, 5, STOP" 

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..] 
"1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..." 

foldrでは、ラムダ関数は、である（リスト要素xを調べ、リストの残りの部分を折るの結果を使用するかどうかを決定することifステートメントを使用することができますaccによって参照されるが、実際にはまだ計算されていない）。

また、関数は再帰呼び出しを含む結果を返しますが、データコンストラクターのフィールドに格納することもできます。つまり、foldrは無限にネストされたデータ構造を生成しますが、の呼び出し元のfoldrは、無限の構造体のどれくらいを見たいかを決めることができるので、依然として呼び出し元がそれを処理できる有限の結果を返すことができます。例は次のようになります。

Prelude> take 10 $ foldr (\x acc -> x + 100 : acc) [] [1..] 
[101,102,103,104,105,106,107,108,109,110] 

ここで私はちょうどのみグラブを、mapと同じ仕事をするfoldrを使用して順番に無限のリストを作成し、無限リストの各要素に100を追加したが、その後take 10よ最初の10人。これは、リストの結果を折り畳む結果がリストコンストラクタ:の2番目のフィールドに格納されているためです。

foldlに渡す関数は、再帰の「どれくらい」を決定しないので、無限リストを処理する能力（実際に有限または無限の結果を返すかどうか）はfoldlでシミュレートできません。使用する。 foldl自体は、foldlの別の呼び出し以外の何かを返す前に、リストの末尾まで繰り返されます。リストが無限であれば、foldlへの別の呼び出し以外の何かを返すことはありません。foldlに渡す関数や、foldrという仕事をするために使用するラッパーに関係なく、何も返しません。

無限のリストの処理だけではありません（それが難解だと思われる場合）。すべてのリストが有限であればはを使用してfoldrと同じ結果を得ることができますが、リスト全体を調べるにはまだロックされていますが、実際に小さな接頭辞が必要な場合は非常に非効率です。