14

厳密と非厳密の定義について質問があります。怠惰のためのHaskellwiki-book（http://en.wikibooks.org/wiki/Haskell/Laziness）は、「ブラックボックスの厳密性分析」のセクションで、次のように主張しています。

[単一のパラメーターをとる関数fを想定します。]関数fは、f undefinedによってエラーが出力され、プログラムが停止する場合に限り、厳密な関数です。

wikiはとは対照的constでid、それぞれ非厳密関数と厳密関数を示しています。

私の質問は、foldl'が厳密であるのに対し、foldlは非厳密な方法で評価され、望ましくないスペースリークを引き起こしているという印象を受けていたということです。

ただし、上記のテストでは、foldlとfoldl'の両方が厳密であると主張しているようです。つまり、パラメータのいずれかが未定義の場合、両方の関数が未定義を生成します。

> Data.List.foldl (+) undefined [1,2,3,4]
    Prelude.undefined
> Data.List.foldl' (+) 0 undefined
    Prelude.undefined
> Data.List.foldl' (+) undefined [1,2,3,4]
    Prelude.undefined
> Data.List.foldl (+) 0 undefined
    Prelude.undefined

誰かが私が欠けているものを説明してもらえますか？

ありがとう！

4

2 に答える 2

11

より適切な定義は次のとおりです。この引数が未定義の場合に関数が未定義の場合、関数は引数で厳密であると言われます。

foldlの次の定義を見てみましょう。

 foldl f s [] = s
 foldl f s (x:xs) = foldl f (f s x) xs

これから、次のことが推測できます。

  1. 最初の式ではsの値は重要ではないfため、厳密ではありません。f
  2. sリストが空でなく、最初の引数で厳密でない可能性があるため、どちらも厳密ではありませんf（think flip const）。
  3. ただし、リスト引数では厳密です。これは、どのような引数であっfてsも、この引数をいわゆるウィークヘッドノーマルフォームに評価する必要があるためです。最も外側のコンストラクターに指示できる場合、代数的データ型の値はWHNFにあります。言い換えると、foldlがlist引数が空のリストであるかどうかを確認することを回避する方法はありません。したがって、少なくともこれまでのところ、リスト値を評価する必要があります。ただし、その値が未定義の場合、2つの方程式のいずれも適用できないため、このアプリケーションfoldl自体は未定義です。

foldlさらに、アキュムレータで厳密ではないという事実から、s多くの場合、使用するのが悪い考えである理由も知ることができます。厳密ではない関数に渡されるfoldlため、システムは実際に用語を評価する理由を認識しません。f s x対応する引数で。確かに、それを評価した場合、それは非厳格性の原則に違反することになります。したがって、リストの長さに応じて、巨大なサンクがアキュムレータに蓄積されます。

((((s `f` x_1) `f` x_2) `f` x_3) ....) `f` x_n)

ここで、のように、fそれ自体が左の引数で厳密である場合(+)、必要に応じてfoldlの結果を評価しようとすると、リストの長さに比例したスタックスペースが必要になります。の場合、の評価はf ... x_n、...左側を表しますが、最初にその左側を評価する必要がf s x_1あります。

したがって、私たちはそれを持っています

foldl (flip const) 0 [1..n]

はn、

foldl const 0 [1..n]

十分な大きさのオーバーフローをスタックしますn。これは、2番目の例ではリストの長さと内容が完全に無関係であり、ほとんどの人が結果が0でなければならないことをすぐに理解するため、人間が機械よりもコンピューティングに優れている場合を示す確かな指標です。

于 2012-11-23T18:38:04.490 に答える
4

あなたが引用するウィキのセクションは、あなたが単一の引数を取る関数を扱っていると仮定しています。の状況foldlは異なります。最初は複数の引数を取るためですが、さらに重要なのは、それらの引数の1つが関数であるためです。foldlいくつかの例をチェックして、引数が厳密である場合を正確に見てみましょう。（以下も適用されることに注意してくださいfoldl'。）

> foldl undefined 0 []
0
> foldl undefined 0 [1]
*** Exception: Prelude.undefined

空のリストのfoldl場合、結合関数を渡す必要はありません。その場合、最初の引数は厳密ではありません。

> foldl (+) undefined [1, 2, 3]
*** Exception: Prelude.undefined
> foldl (+) 0 undefined
*** Exception: Prelude.undefined

(+)結合関数として渡す場合、開始値とリストで厳密になります。別の組み合わせ関数を使用した別の例を次に示します。

> foldl (flip (:)) undefined [1, 2, 3]
[3,2,1*** Exception: Prelude.undefined

面白い。開始値は未定義ですが、呼び出しがfoldl例外をスローする前にいくつかの結果を生成したように見えます。これはどうですか：

> let (x:xs) = foldl (flip (:)) undefined [1, 2, 3]
> x
3

そこに例外はありません。したがって、恐ろしいにぶつかることなく、部分的な結果を得ることができます。なんで？foldlPrelude.undefined

変更されたのは、に渡した結合関数だけですfoldl。(+)タイプは（大まかに）ですInt -> Int -> Intがflip (:)、タイプは[a] -> a -> [a]です。弱い頭の正常な形では3 + ((2 + 1) + undefined)なく、評価されるように減らす必要があるのに対し、弱い頭の正常な形であり、それ以上の評価を必要とせず、特にの評価を必要としない。undefined(3:(2:(1:undefined))) undefined

于 2012-11-23T18:06:54.663 に答える