2

これら 2 つのコードの違い ( に関してx) はわかりませんが、最初のコードは次のように完了します。

$ foldr (\x y -> if x == 4 then x else x + y) 0 [1,2 .. ]
10

そして2番目のものはそうではありません(少なくともGHCiでは):

$ foldr (\x (y, n) -> if x == 4 then (x, n) else (x + y, n + 1)) (0, 0) [1,2 .. ]
.......

最初の例のように、ヒットしたときに 2 番目の例が完了しない原因は何x == 4ですか?

xとの両方x == 4( a 内)に強打パターンを追加しようとしましletたが、どちらも違いはないようです。

4

3 に答える 3

4

2番目の例には、2つの関連する問題があります。

foldr右結合の入れ子、つまりfoldr f z [a, b, c]=を生成することを思い出してくださいf a (f b (f c z))。したがって、指定する関数の2番目の引数は、残りのリスト全体を折りたたむ最終的なfoldr値を表します。無限リストの場合、これは、別の遅延無限データ構造を生成するか、最初の例のように、ある時点で2番目のパラメーターを完全に無視する場合にのみ可能です。

2番目の例では、常に入力タプルの2番目の項目を使用して、結果のタプルの2番目の項目を計算します。したがって、無限リストに適用すると、無限後退になります。0開始値はリストの最後に配置されるため、「開始」値として指定しても役に立ちませんfoldr。これは、無限のリストには明らかにありません。値を変更せずに渡したいようですが、で始まる（またはおそらく「終了する」）値を持っている必要があります！

これだけでは、結果の2番目の項目が終了しなくなります。結果の最初の項目は明確に定義されているか、少なくともそうなる可能性があります。ここでの問題は、パターンマッチングが評価を強制することです。これにより、折り畳み全体が終了するまで結果が生成されなくなります。これはいくつかの方法で回避できますが、使用するだけで十分に簡単fstです。最初の項目が期待どおりのタプルで構成される結果が得られるはずです（ただし、上記で説明したように、2番目の項目は未定義です）。snd\x yn -> if x == 4 then (x, snd yn) else (x + fst yn, snd yn + 1)

于 2012-10-24T17:01:44.803 に答える
3

これは、パターン マッチング/評価が行われる方法です。f = \x (y, n) -> ...定義したとおりにすると、

foldr f (0, 0) [1,2 .. ] =
   f 1 (foldr f (0,0) [2..]) =
   (\x (y, n) -> ...) 1 (foldr f (0,0) [2..])

そして、その(y,n)パターンは厳密に一致するため、何かを計算するには、2 番目の引数 ( foldr .. [2..]) を計算する必要があり、それが必要foldr .. [3..]であり、それが永遠に繰り返されます。

~(「反駁不可能なパターン」と呼ばれます)を使用して、パターン マッチを非厳密にすることができます。これにより、動作が多少変わります。

> foldr (\x ~(y,n) -> if x == 4 then (x,n) else (x+y,n+1)) (0,0) [1..]
(10,

(反論可能なバージョンは、タプルの最初の要素でさえ計算できません。)

于 2012-10-24T16:57:32.450 に答える
3

最初のものは「アキュムレータ」（つまりy）からの値を使用しませんが、2番目のものは を使用して使用しnます。コンピューティングnでは、リスト全体を折り畳む必要があるため、終了することはありません。どんなに厳しくしてもそれは解決しません。

実際、あなたのアルゴリズムは、あなたが思っていることをしません。foldrの動作を と混同している可能性がありfoldlます。何らかの方法で を計算できたとしてもn、その値は無限大になります。考える最良の方法は、リスト内のfoldrすべてを最初の関数に置き換え、端子を2番目の値に置き換えることです。(:)[]

于 2012-10-24T16:52:23.167 に答える