73

Learn You A Haskellからの次の一節に問題があります(素晴らしい本です。それを否定するのではありません)。

大きな違いの 1 つは、右の折り畳みは無限リストで機能するのに対し、左の折り畳みは機能しないことです! 端的に言えば、ある時点で無限リストを右から折りたたむと、最終的にリストの先頭に到達します。しかし、ある点で無限リストを取り、それを左から折りたたもうとすると、決して終わりに達することはありません!

私はこれを理解していません。無限リストを右から折り畳もうとすると、無限の点から開始する必要がありますが、これは実際には起こっていません (これを行うことができる言語を誰かが知っている場合は、教えてください:p ）。少なくとも、Haskell の実装によれば、そこから開始する必要があります。Haskell では、foldr と foldl は、リスト内のどこから折り畳みを開始するかを決定する引数を取らないためです。

無限リストを取得し、定義されたインデックスから直接折りたたみを開始すると、最終的に終了することは理にかなっているからです。左折からどこから始めても構いません。無限に向かってフォールドします。ただし、foldr と foldlはこの引数を取らないため、引用は意味がありません。Haskell では、無限リストの左折と右折の両方が終了しません。

私の理解は正しいですか、それとも何か不足していますか?

4

5 に答える 5

90

ここで重要なのは怠惰です。リストを折りたたむために使用している関数が厳密である場合、リストが無限であるとすると、左折りも右折りも終了しません。

Prelude> foldr (+) 0 [1..]
^CInterrupted.

ただし、それほど厳密でない関数を折りたたむと、終了する結果が得られる可能性があります。

Prelude> foldr (\x y -> x) 0 [1..]
1

無限のデータ構造である結果を得ることができるので、ある意味では終了しませんが、それでも怠惰に消費できる結果を生成することができます。

Prelude> take 10 $ foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10]

ただし、foldl怠惰であるかどうかにかかわらず、最も外側の関数呼び出しを評価することはできないため、これはでは機能しません。

Prelude> foldl (flip (:)) [] [1..]
^CInterrupted.
Prelude> foldl (\x y -> y) 0 [1..]
^CInterrupted.

左と右の折り畳みの主な違いは、リストがトラバースされる順序（常に左から右）ではなく、結果の関数適用がネストされる方法であることに注意してください。

  • を使用foldrすると、「内側」にネストされます

    foldr f y (x:xs) = f x (foldr f y xs)

    ここで、最初の反復は、の最も外側のアプリケーションになりfます。したがって、f2番目の引数が常に評価されるとは限らないか、2番目の引数を強制せずにデータ構造の一部を生成できるように、怠惰になる機会があります。

  • を使用foldlすると、それらは「外側」にネストされます

    foldl f y (x:xs) = foldl f (f y x) xs

    ここでは、の最も外側のアプリケーションに到達するまで何も評価できません。これは、厳密fであるかどうかに関係なく、無限リストの場合には決して到達しません。f

于 2011-09-13T05:17:21.790 に答える
18

キーワードは「いつか」です。

ある時点で無限リストを取得し、それを右から折りたたむと、最終的にリストの先頭に到達します。

そうです、無限リストの「最後の」要素から始めることはできません。しかし、著者のポイントは次のとおりです。できると仮定してください。そこからかなり離れたポイント (エンジニアにとって、これは無限に「十分近い」) を選択し、左に折り始めます。最終的には、リストの先頭にたどり着きます。同じことが左の折り方には当てはまりません。そこからかなり離れた点を選択し (そして、それをリストの先頭に「十分に近い」と呼びます)、右方向に折り畳み始めると、まだ無限に進むことができます。

秘訣は、無限に行く必要がない場合があるということです。あなたはそこに行く必要さえないかもしれません。しかし、事前にどこまで進める必要があるか分からない場合があります。その場合、無限リストは非常に便利です。

簡単なイラストはfoldr (:) [] [1..]. 折りをしましょう。

それを思い出してくださいfoldr f z (x:xs) = f x (foldr f z xs)。無限のリストでは、実際には何が問題ではないので、イラストを乱雑にする代わりにそのzままにしておきますz[]

foldr (:) z (1:[2..])         ==> (:) 1 (foldr (:) z [2..])
1 : foldr (:) z (2:[3..])     ==> 1 : (:) 2 (foldr (:) z [3..])
1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..])
1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] )

理論的には右foldrからの折り畳みであるにも関わらず、この場合、実際には結果のリストの個々の要素を左から開始する方法を参照してください。したがって、このリストから、折り畳みを生成でき、それ以上評価する必要がないことがはっきりとわかります。take 3[1,2,3]

于 2011-09-13T19:08:16.307 に答える
12

Haskell では、遅延評価のために無限リストを使用できることを思い出してください。したがって、`[1..] は無限に長いにもかかわらず、head [1..]ちょうど 1 であり、 2 です。head $ map (+1) [1..]それがわからない場合は、しばらく停止して遊んでください。あなたがそれを手に入れたら、読んでください...

あなたの混乱の一部は、foldlandfoldrが常にどちらか一方の側から始まるということだと思います。したがって、長さを指定する必要はありません。

foldr非常に単純な定義を持っています

 foldr _ z [] = z
 foldr f z (x:xs) = f x $ foldr f z xs

なぜこれが無限リストで終了するのでしょうか、よく試してください

 dumbFunc :: a -> b -> String
 dumbFunc _ _ = "always returns the same string"
 testFold = foldr dumbFunc 0 [1..]

ここではfoldr、"" (値は重要ではないため) と自然数の無限リストに渡します。これは終了しますか？はい。

終了する理由は、Haskell の評価が遅延項書き換えに相当するためです。

そう

 testFold = foldr dumbFunc "" [1..]

になります (パターン マッチングを可能にするため)

 testFold = foldr dumbFunc "" (1:[2..])

これは (フォールドの定義から) と同じです。

 testFold = dumbFunc 1 $ foldr dumbFunc "" [2..]

の定義により、次のdumbFuncように結論付けることができます。

 testFold = "always returns the same string"

これは、何かを実行するが、時には遅延する関数がある場合に、より興味深いものになります。例えば

foldr (||) False

リストにTrue要素が含まれているかどうかを調べるために使用されます。これを使用して、渡された関数がリストのいくつかの要素に対して true である場合にのみany返す高階関数 n を定義できます。True

any :: (a -> Bool) -> [a] -> Bool
any f = (foldr (||) False) . (map f)

遅延評価の良いところは、最初の要素に遭遇すると停止することeです。f e == True

一方、これは には当てはまりませんfoldl。なんで？まあ、本当に単純なfoldlように見えます

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

さて、上記の例を試してみたらどうなるでしょう

testFold' = foldl dumbFunc "" [1..]
testFold' = foldl dumbFunc "" (1:[2..])

これは次のようになります。

testFold' = foldl dumbFunc (dumbFunc "" 1) [2..]

それで

testFold' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..]

などなど。Haskell は常に最も外側の関数を最初に評価するため、どこにもたどり着くことはできません (つまり、簡単に言えば遅延評価です)。

これの素晴らしい結果の 1 つは、foldlout を実装できますがfoldr、その逆はできないということです。これは、他のほとんどすべてを実装するために使用するものであるため、何らかの深遠な意味でfoldr、すべての高階文字列関数の中で最も基本的なものであることを意味します。tail を再帰的に実装し、そこからパフォーマンスを向上 させることができるfoldlため、時々使用したい場合があります。foldl

于 2011-09-13T06:00:32.583 に答える
0

Haskell wikiにわかりやすい説明があります。さまざまな種類のフォールドおよびアキュムレータ関数を使用した段階的な削減を示しています。

于 2015-04-10T06:47:40.087 に答える
-3

あなたの理解は正しいです。著者は Haskell の遅延評価システム (fold を含まないさまざまな関数に無限リストを渡すことができ、答えを返すために必要なだけ評価する) について話そうとしているのではないかと思います。しかし、著者がそのパラグラフで何かをうまく説明しておらず、それが間違っていることに同意します。

于 2011-09-13T05:12:08.187 に答える