13

Haskellには、、、 についての良い質問と回答がたくさんあります。foldlfoldrfoldl'

だから今私は知っています：
1）foldl怠惰です
2）foldlスタックを爆破する可能性があるので使用しないでください
3）foldl'厳密なので代わりに使用してください（ish）

評価方法foldl：
1）大量のサンクが作成されます
2）Haskellがサンクの作成を完了した後、サンクが削減され
ます3）サンクが多すぎる場合はスタックがオーバーフローします

私が混乱していること：
1）なぜすべてのサンクの後に削減が発生しなければならないのですか？
2）なぜfoldl同じように評価されないのfoldl'ですか？これは単なる実装の副作用ですか？
3）定義から、末尾再帰を使用して効率的に評価できるようにfoldl見えます-関数が実際に効率的に評価されるかどうかをどのように判断できますか？プログラムをクラッシュさせたくないのであれば、Haskellでの評価の順序について心配し始めなければならないようです。

前もって感謝します。の評価についての私の理解が正しいかどうかはわかりませんfoldl。必要に応じて修正を提案してください。

更新：私の質問への答えは、正規形、弱い正規形、および頭の正規形、およびそれらのHaskellの実装と関係があるようです。
ただし、結合関数をより熱心に評価すると、別の結果（クラッシュまたは不要な評価）が発生する例をまだ探しています。

4

4 に答える 4

8

簡単に言うと、foldl fでは、必ずしもf厳密であるとは限らないため、前もってサンクを減らすことは熱心すぎる可能性があります。ただし、実際には通常はそうなので、ほとんどの場合、を使用する必要がありますfoldl'。

別の質問の評価順序と動作について、より詳細な説明foldlfoldl'を書きました。かなり長いですが、少しわかりやすくなると思います。

于 2011-09-20T15:24:19.963 に答える
4

あなたが知っている、それは定義上：

foldl op start (x1:x2:...:xN:[]) = ((start `op` x1) `op` x2) ...

これを行うfoldlの行は次のとおりです。

foldl op a (x:xs) = foldl op (a `op` x) xs

これが末尾再帰であることは正しいですが、式が

(a `op` x)

怠惰であり、リストの最後に、巨大な式が作成され、それが縮小されます。foldl'との違いは、上記の式がすべての再帰で評価を強制されることです。したがって、最終的には、弱いヘッドの通常の形式の値が得られます。

于 2011-09-20T15:28:12.733 に答える
1

結合関数をもっと熱心に評価すると別の結果が得られる例をまだ探しています

一般的な経験則では、決して使用することはありませんfoldl。を使用する必要がある場合を除いてfoldl'、常にを使用してください。なぜそれを避けるべきなのかを理解するのに十分知っていると思います。foldrfoldl

参照：Real World Haskell>関数型プログラミング＃左折り、怠惰、スペースリーク

しかし、あなたの質問は無視しfoldrます。気の利いたことは、答えを出す前にリスト全体をトラバースする必要がfoldrある一方で、増分結果を生成できることです。foldl'これは、foldrの怠惰により、無限のリストで機能できることを意味します。この種のことについて詳しく説明する質問と回答もあります。

それを提起したので、私はあなたの質問に簡潔に答えることを試みさせてください。

1）なぜすべてのサンクの後に削減が発生しなければならないのですか？

削減は、厳密なポイントでのみ発生します。たとえば、IOの実行は厳密なポイントです。を持たない追加の厳密点を追加するためにfoldl'使用します。seqfoldl

2）foldlがfoldlのように評価されないのはなぜですか？これは単なる実装の副作用ですか？

の追加の厳格さのためにfoldl'

3）定義から、foldlは私には末尾再帰関数のように見えます-関数が実際に効率的に評価されるかどうかをどのように判断できますか？プログラムをクラッシュさせたくないのであれば、Haskellでの評価の順序について心配し始めなければならないようです。

遅延評価についてもう少し学ぶ必要があります。遅延評価はHaskellに限ったことではありませんが、Haskellは、怠惰がデフォルトである非常に少数の言語の1つです。初心者の場合は、常に使用することを忘れないfoldl'でください。問題はありません。

怠惰が実際にいつかあなたを困らせるなら、それはおそらくあなたが怠惰とハスケルの厳格さのポイントを理解していることを確認するべきであるときです。理論上の日は、デフォルトで怠惰な学習の厳格さのポイントであると言うかもしれません。

参照：PLAI>パートIII：怠惰

于 2011-09-20T18:17:29.713 に答える
0

プログラムをクラッシュさせたくないのであれば、Haskellでの評価の順序について心配し始めなければならないようです。

私の意見では、プログラムをクラッシュさせたくない場合の最良のオプションは次のとおりです（費やした労力あたりの歩留まりの観点から良いものから悪いものへとランク付けされています）：1。十分なリソースを与えます。2.アルゴリズムを改善します。3.マイクロ最適化を実行します（そのうちの1つはですfoldl'）。

ですから、評価の順番を気にするのではなく、まず何を評価するのかを気にしたいのです（それでfoldr十分ですか？それを折りたたむことなくできますか？）。その前に、使用可能なスタックスペースを増やします。

プログラム全体を8MBのRAMに制限しませんか？では、なぜスタックスペースを制限するのでしょうか。スタックスペースを4GBに増やすだけで、（ヒープメモリの場合のように）何かが実際に大量のスタックスペースを占有するときに心配し始めます。

foldlそして、どのように怠惰であるかという質問にいくらか答えるために：

foldl (\x y -> y) undefined [undefined, 8] -- evaluates to 8
foldl' (\x y -> y) undefined [undefined, 8] -- fails to evaluate
于 2011-09-20T17:22:40.017 に答える