11

私は Haskell の初心者で、foldr/foldl の説明をいくつか読んだ後でさえ、以下の異なる結果が得られる理由がわかりません。説明は何ですか？

Prelude> foldl (\_ -> (+1)) 0 [1,2,3]
4
Prelude> foldr (\_ -> (+1)) 0 [1,2,3]
3

ありがとう！

4

5 に答える 5

8

これは、引数の順序が逆になっているためですfoldl。それらの型シグネチャを比較します。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldr :: (a -> b -> b) -> b -> [a] -> b

ご覧のとおり、 を使用するコードではfoldl、リストを無視してアキュムレータを繰り返しインクリメントします。しかし、 を使用したコードではfoldr、アキュムレータに触れることさえせず、リストの要素をインクリメントするだけです。最後の要素が3であるため、結果は3 + 1 = 4です。

代わりに文字列とも呼ばれる文字のリストを使用すると、間違いをより簡単に確認できます。

ghci> フォルダ (\_ -> (+1)) 0 ['a','b','c']
3
ghci> foldl (\_ -> (+1)) 0 ['a','b','c']

:1:20:
    (Num Char) のインスタンスがありません
      リテラル `0' から生じる
    考えられる修正: (Num Char) のインスタンス宣言を追加します
    `foldl' の 2 番目の引数、つまり `0'
    式: foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c']
    「それ」の方程式では：
        it = foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c']
ghci>
于 2011-05-18T20:03:37.240 に答える
7

このfoldl場合、ラムダは最初の引数としてアキュムレータに渡され、2 番目の引数としてリスト要素が渡されます。このfoldr場合、ラムダには最初の引数としてリスト要素が渡され、2 番目の引数としてアキュムレータが渡されます。

ラムダは最初の引数を無視し、2 番目の引数に 1 をfoldl追加するため、最後の要素に 1 を追加しているfoldr場合、リスト内の要素の数を数えています。

于 2011-05-18T20:09:52.483 に答える
6

ではfoldl f、アキュムレータは の左の引数でfあり、これを無視しているため1 +、最後の要素が返されます。ではfoldr、アキュムレータが正しい引数であるため、アイテムごとにアキュムレータを 1 ずつ増やして、効果的にリストの長さを指定します。

f x y = y + 1

foldl f 0 [1, 2, 3]
= f (f (f 0 1) 2) 3 
= f ignored 3
= 3 + 1
= 4

foldr f 0 [1, 2, 3]
= f 1 (f 2 (f 3 0)))
= f ignored (f ignored (f ignored 0)))
= ((((0 + 1) + 1) + 1)
= 3
于 2011-05-18T20:02:11.707 に答える
6

この違いは、次の 2 つの理由によるものです。

  • 累積関数への 1 つの入力を破棄し、定数関数を別の入力に適用しています。
  • 累積関数への引数の順序は、2 つの間で異なります。

左折りでは、アキュムレータは破棄する引数であるため、リスト内の次の項目に適用するたびに(+1)、最終的に最後の要素に 1 を加えた値を返します。

正しいフォールドでは、accumulator が保持される引数であるため(+1)、前の結果に適用するたびに、最初は 0 であり、3 回インクリメントされます (リスト内の項目ごとに)。

より明確に異なる入力値を使用すると、ここで何が起こっているかを簡単に確認できる場合があります。

Prelude> foldl (\_ -> (+1)) 100 [5,6,7]
8
Prelude> foldr (\_ -> (+1)) 100 [5,6,7]
103

繰り返しますが、「最後の引数に 1 を加えたもの」と「リストの長さと初期値を加えたもの」です。

于 2011-05-18T20:03:33.920 に答える
5

カリー化とポイントフリースタイルを削除すると役立つ場合があります。あなたの2つの式は次のものと同等です：

foldl (\acc x ->   x + 1) 0 [1,2,3]
foldr (\x acc -> acc + 1) 0 [1,2,3]

そのように見ると、結果はより明白に見えるはずです

于 2011-12-30T02:48:22.390 に答える