87

誰がどのように機能するか説明できますfoldrか?

次の例を見てください。

Prelude> foldr (-) 54 [10, 11]
53
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]
12.0

私はこれらの処刑について混乱しています。助言がありますか？

4

11 に答える 11

166

foldr を理解する最も簡単な方法は、折り畳んでいるリストをシュガーなしで書き直すことです。

[1,2,3,4,5] => 1:(2:(3:(4:(5:[]))))

ここfoldr f xで行うことは、それぞれ:をf中置形式で置き換え、結果[]をx評価することです。

例えば：

sum [1,2,3] = foldr (+) 0 [1,2,3]

[1,2,3] === 1:(2:(3:[]))

それで

sum [1,2,3] === 1+(2+(3+0)) = 6
于 2009-11-19T13:32:32.003 に答える
101

foldrリストの右端から始まり、指定した関数を使用して、各リストエントリをアキュムレータ値と結合します。結果は、すべてのリスト要素で「折りたたまれた」後のアキュムレータの最終値です。そのタイプは次のとおりです。

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

これから、（タイプのa）リスト要素が指定された関数の最初の引数であり、（タイプのb）アキュムレータが2番目の引数であることがわかります。

最初の例： 

Starting accumulator = 54
11 -   54  = -43
10 - (-43) =  53

        ^  Result from the previous line

 ^ Next list item

だからあなたが得た答えは53でした。

2番目の例：

Starting accumulator = 54
(6  + 54) / 2 = 30
(10 + 30) / 2 = 20
(4  + 20) / 2 = 12
(12 + 12) / 2 = 12

したがって、結果は12になります。

編集：私は追加するつもりでした、それは有限リストのためです。 foldr無限のリストでも機能しますが、最初に有限の場合に頭を悩ませるのが最善だと思います。

于 2009-11-18T17:47:55.730 に答える
44

と の違いを理解するのに役立ちfoldrますfoldl。なぜfoldr「右折」と呼ばれるのですか？

最初は、右から左に要素を消費したためだと思いました。しかし、両方ともリストを左から右に消費しますfoldr。foldl

  • foldl 左から右に評価します (左結合)
  • foldr 右から左に評価します (右結合)

この区別は、結合性が重要な演算子を使用する例で明確にすることができます。オペレーターの「eats」など、人間の例を使用できます。

foodChain = (human : (shark : (fish : (algae : []))))

foldl step [] foodChain
  where step eater food = eater `eats` food  -- note that "eater" is the accumulator and "food" is the element

foldl `eats` [] (human : (shark : (fish : (algae : []))))
  == foldl eats (human `eats` shark)                              (fish : (algae : []))
  == foldl eats ((human `eats` shark) `eats` fish)                (algae : [])
  == foldl eats (((human `eats` shark) `eats` fish) `eats` algae) []
  ==            (((human `eats` shark) `eats` fish) `eats` algae)

これのセマンティクスfoldlは次のとおりです。人間がサメを食べ、次にサメを食べた同じ人間が魚を食べる、などです。食べる人はアキュムレーターです。

これを次のように対比してください。

foldr step [] foodChain
    where step food eater = eater `eats` food.   -- note that "eater" is the element and "food" is the accumulator

foldr `eats` [] (human : (shark : (fish : (algae : []))))
  == foldr eats (human `eats` shark)                              (fish : (algae : []))))
  == foldr eats (human `eats` (shark `eats` (fish))               (algae : [])
  == foldr eats (human `eats` (shark `eats` (fish `eats` algae))) []
  ==            (human `eats` (shark `eats` (fish `eats` algae)

これのセマンティクスfoldrは次のとおりです。人間は、すでに魚を食べたサメを食べ、サメはすでに藻を食べています。食べ物はアキュムレータです。

どちらも左から右にイーターfoldlをfoldr「はがす」ため、foldl を「左折り」と呼ぶ理由はありません。代わりに、評価の順序が重要です。

于 2012-08-09T20:12:09.210 に答える
26

foldrのまさに定義について考えてみましょう:

 -- if the list is empty, the result is the initial value z
 foldr f z []     = z                  
 -- if not, apply f to the first element and the result of folding the rest 
 foldr f z (x:xs) = f x (foldr f z xs)

したがって、たとえばfoldr (-) 54 [10,11]must equal (-) 10 (foldr (-) 54 [11])、つまり、再度展開すると equal になり(-) 10 ((-) 11 54)ます。したがって、内部演算は11 - 54、つまり -43 です。そして外側の演算は10 - (-43)、つまり です。10 + 43したがって53、ご覧のとおりです。2 番目のケースでも同様の手順を実行すると、結果がどのように形成されるかがわかります。

于 2009-11-18T17:46:25.493 に答える
22

foldrは右から折りたたむことを意味するため、 がfoldr (-) 0 [1, 2, 3]生成され(1 - (2 - (3 - 0)))ます。比較するとfoldl、 が生成され(((0 - 1) - 2) - 3)ます。

演算子が交換可能 foldlではなくfoldr、異なる結果が得られる場合。

あなたの場合、最初の例(10 - (11 - 54)) は 53 に展開されます。

于 2009-11-18T17:40:55.427 に答える
10

これを理解する簡単な方法foldrは次のとおりです。すべてのリスト コンストラクターを、提供された関数のアプリケーションに置き換えます。最初の例は次のように変換されます。

10 - (11 - 54)

から：

10 : (11 : [])

Haskell Wikibook から得た良いアドバイスは、ここで役立つかもしれません。

原則として、foldr無限の可能性があるリスト、または折り畳みがデータ構造を構築しているリスト、およびfoldl'リストが有限であることがわかっており、単一の値になる場合に使用する必要があります。foldl(チェックマークなし) はめったに使用しないでください。

于 2009-11-19T22:23:30.307 に答える
7

http://foldr.comは面白いイラストだといつも思っていました。Lambda the Ultimate の投稿を参照してください。

于 2009-11-18T20:12:45.890 に答える
2

map、foldl、foldr を単純な方法で実装すると、それらがどのように機能するかを説明できると思います。実際の例も理解に役立ちます。

  myMap f [] = []
  myMap f (x:xs) = f x : myMap f xs

  myFoldL f i [] = i
  myFoldL f i (x:xs) = myFoldL f (f i x) xs

  > tail [1,2,3,4] ==> [2,3,4]
  > last [1,2,3,4] ==> 4
  > head [1,2,3,4] ==> 1
  > init [1,2,3,4] ==> [1,2,3]

  -- where f is a function,
  --  acc is an accumulator which is given initially
  --  l is a list.
  --
  myFoldR' f acc [] = acc
  myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l)

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

  > map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]
  > myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]

  > foldl (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125
  > myFoldL (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125

    foldl from above: Starting accumulator = 54
      (12  + 54) / 2 = 33
      (4 + 33) / 2 = 18.5
      (10  + 18.5) / 2 = 14.25
      (6 + 14.25) / 2 = 10.125`

 > foldr (++) "5" ["1", "2", "3", "4"] ==> "12345"

 > foldl (++) "5" ["1", "2", "3", "4"] ==> “51234"

 > foldr (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
 > myFoldR' (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
 > myFoldR (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12

    foldr from above: Starting accumulator = 54
        (6  + 54) / 2 = 30
        (10 + 30) / 2 = 20
        (4  + 20) / 2 = 12
        (12 + 12) / 2 = 12
于 2017-05-30T05:44:29.273 に答える
1

わかりました、引数を見てみましょう:

  • 関数 (リスト要素と、それが返す値と同じ種類の値 (可能な部分的な結果) を取る);
  • 空リストの特殊なケースに対する初期結果の仕様
  • リスト;

戻り値:

  • いくつかの最終結果

最初にリストの最後の要素と空のリストの結果に関数を適用します。次に、この結果と前の要素を使用して関数を再適用し、現在の結果とリストの最初の要素を取得して最終結果を返すまで繰り返します。

Fold は、要素と以前の折り畳み結果を受け取る関数を使用して、最初の結果の周りにリストを「折り畳み」ます。これを要素ごとに繰り返します。そのため、foldr はこれをリストの最後、つまりリストの右側から開始します。

folr f emptyresult [1,2,3,4]に変わります f(1, f(2, f(3, f(4, emptyresult) ) ) ) 。ここで、評価の括弧に従ってください。それだけです。

注意すべき重要な点の 1 つは、指定された関数fが独自の戻り値を 2 番目の引数として処理する必要があることです。これは、両方が同じ型でなければならないことを意味します。

出典:役立つと思われる場合は、必須の非カリー化された JavaScript の観点から見た私の投稿。

于 2013-04-06T18:48:29.027 に答える