function - foldrとfoldlの詳細な説明と例

Question

私はさまざまな折り目と折り目一般、および他のいくつかを見てきましたが、それらはそれをかなりよく説明しています。

この場合、ラムダがどのように機能するかについてはまだ問題があります。

foldr (\y ys -> ys ++ [y]) [] [1,2,3]

誰かがそのステップバイステップを実行して、それを私に説明しようとすることができますか？

また、どのようにfoldl機能しますか？

Answer 1

foldrは簡単なものです：

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

それはどういうわけか（:)に似た関数を取ります、

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

空のリスト[]に類似した値、

[] :: [a]

いくつかのリストの各：と[]を置き換えます。

次のようになります。

foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e))

foldrをステートマシンエバリュエーターとして想像することもできます。

fは遷移であり、

f :: input -> state -> state

eは開始状態です。

e :: state

foldr（foldRIGHT）は、右端から開始して、入力のリストに対して遷移fと開始状態eを使用してステートマシンを実行します。中置記法のfを想像してみてください。

foldl（foldLEFT）は同じfrom-LEFTを実行しますが、中置記法で記述された遷移関数は、入力引数を右から取得します。したがって、マシンは左端から始まるリストを消費します。Pacmanは、（a-> b-> b）ではなく口（b-> a-> b）があるため、リストを-LEFTから右に開いた口で消費します。

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

これを明確にするために、関数(-)を遷移として想像してください。

foldl (-) 100 [1]         = 99 = ((100)-1)
foldl (-) 100 [1,2]       = 97 = (( 99)-2) = (((100)-1)-2)
foldl (-) 100 [1,2,3]     = 94 = (( 97)-3)
foldl (-) 100 [1,2,3,4]   = 90 = (( 94)-4)
foldl (-) 100 [1,2,3,4,5] = 85 = (( 90)-5)

foldr (-) 100 [1]         = -99 = (1-(100))
foldr (-) 100 [2,1]       = 101 = (2-(-99)) = (2-(1-(100)))
foldr (-) 100 [3,2,1]     = -98 = (3-(101))
foldr (-) 100 [4,3,2,1]   = 102 = (4-(-98))
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102))

リストが無限大になる可能性があり、評価を怠惰にする必要がある状況では、foldrを使用することをお勧めします。

foldr (either (\l ~(ls,rs)->(l:ls,rs))
              (\r ~(ls,rs)->(ls,r:rs))
      ) ([],[]) :: [Either l r]->([l],[r])

また、リスト全体を使用して出力を生成する場合は、厳密なバージョンのfoldl（foldl'）を使用することをお勧めします。遅延評価と組み合わせた極端に長いリストが原因で、パフォーマンスが向上し、スタックオーバーフローまたはメモリ不足の例外（コンパイラによって異なります）が発生しなくなる可能性があります。

foldl' (+) 0 [1..100000000] = 5000000050000000
foldl  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
foldr  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci

最初の一歩は、リストの1つのエントリを作成し、それを評価して、それを消費します。

2つ目は、最初に非常に長い式を作成し、（（...（（0 + 1）+2）+3）+ ...）でメモリを浪費し、その後すべてを評価します。

3つ目は、2つ目と似ていますが、他の式を使用しています。

Answer 2

使用する

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

と

k y ys = ys ++ [y]

開梱しましょう：

foldr k [] [1,2,3]
= k 1 (foldr k [] [2,3]
= k 1 (k 2 (foldr k [] [3]))
= k 1 (k 2 (k 3 (foldr k [] [])))
= (k 2 (k 3 (foldr k [] []))) ++ [1]
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1]
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1]
= ((([]) ++ [3]) ++ [2]) ++ [1]
= (([3]) ++ [2]) ++ [1]
= ([3,2]) ++ [1]
= [3,2,1]

Answer 3

の定義foldrは次のとおりです。

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

だからここにあなたの例の段階的な削減があります：

  foldr (\y ys -> ys ++ [y]) [] [1,2,3]
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3])
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1]
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1]
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1]
= [] ++ [3] ++ [2] ++ [1]
= [3,2,1]

Answer 4

中置記法はおそらくここでより明確になります。

定義から始めましょう：

foldr f z []     = z
foldr f z (x:xs) = x `f` (foldr f z xs)

簡潔にするために、のg代わりに書いてみましょう(\y ys -> ys ++ [y])。次の行は同等です。

foldr g [] [1,2,3]
1 `g` (foldr g [] [2,3])
1 `g` (2 `g` (foldr g [] [3]))
1 `g` (2 `g` (3 `g` (foldr g [] [])))
1 `g` (2 `g` (3 `g` []))
(2 `g` (3 `g` [])) ++ [1]
(3 `g` []) ++ [2] ++ [1]
[3] ++ [2] ++ [1]
[3,2,1]

Answer 5

これを最初に覚える私の方法は、結合法則の敏感な 減算演算を使用することです。

foldl (\a b -> a - b) 1 [2] = -1
foldr (\a b -> a - b) 1 [2] = 1

次に、foldlはリストの左端または最初の要素からfoldr開始しますが、リストの右端または最後の要素から開始します。リストには要素が1つしかないため、上記では明らかではありません。

私のニーモニックはこれです：またはは2leftつrightのことを説明します：

• マイナス（-）記号の配置
• リストの開始要素