なぜこれらの折り目が頭/尾で止まるのですか？

Question

私はlearnyouahaskell.comを読んでおり、現在フォールドを調査中です。この本では、これらの例があります

maximum' :: (Ord a) => [a] -> a 
maximum' = foldr1 (\x acc -> if x > acc then x else acc) 

reverse' :: [a] -> [a] 
reverse' = foldl (\acc x -> x : acc) [] 

product' :: (Num a) => [a] -> a 
product' = foldr1 (*) 

filter' :: (a -> Bool) -> [a] -> [a] 
filter' p = foldr (\x acc -> if p x then x : acc else acc) [] 

head' :: [a] -> a 
head' = foldr1 (\x _ -> x) 

last' :: [a] -> a 
last' = foldl1 (\_ x -> x) 

私はhead'とtail'を除き、それらのすべてを理解しています。

バイナリ関数をアキュムレータとリストの各要素に順番に適用し、すべてのリストを調べる必要があると私は理解しています。なぜこれは頭（または尾）に止まるのですか？

私は_（アンダースコア）は「何でも」または「気にしない」ことを意味しますが、どのようにすべてのリストを通過するのでしょうか？

Answer 1

のは、最初のfoldr1の定義を見てみましょう：

foldr1 :: (a -> a -> a) -> [a]  -> a 
foldr1 f    [x]  = x 
foldr1 f    (x : xs) = f x (foldr1 f xs) 

その後、言う、リストにあなたの関数head'の呼び出し、

​​

を検討し、[2, 3, 5]：

head' [2, 3, 5] 

は今、head'の右手側に充填して[2, 3, 5]が(2 : 3 : 5 : [])ための糖衣構文であることを

foldr1 (\x _ -> x) [2, 3, 5] 

リコールを提供します。だから、foldr1の定義の第二の場合は適用され、我々は無視パラメータ_にバインドされたばかりxとfoldr1 (\x _ -> x) (3 : 5 : [])にバインドされたばかり2でのアプリケーションの結果を減らし、今

(\x _ -> x) 2 (foldr1 (\x _ -> x) (3 : 5 : []) 

をもたらします。 2に置き換え xとラムダ抽象の右側は何残されている：遅延評価は無視引数 foldr1 (\x _ -> x) (3 : 5 : [])が残されていることになることを

2 

注未評価など-、これはうまくいけば、あなたのquestion-に答えますリストの残りの部分を処理する前に再帰が停止します。

Answer 2

foldrは、現在の「実行中の合計」アイテムのソートと新しいアイテムの2つのアイテムを結合します。

(\x _ -> x)は、新しいアイテムを取り出して元のままにしておくので、残りのアイテムはすべて無視されます。

はのは、それを拡張してみましょう：

foldr1 (\x _ -> x) [1..100000] 
= (\x _ -> x) 1 (foldr (\x _ -> x) [2..100000]) 
= 1 

(foldr (\x _ -> x) [2..100000])用語が必要とされていないので、それは（それがアクションで遅延評価だ、または不作為ではなく）を評価するので、これは速く走るされていません。 (\_ x -> x)で

---

、新しいアイテムが取得され、古いものは無視されます - これは、リストの最後まで起こっを続けるので、あなたは最後の要素を取得します。それは他のものを避けるものではなく、最後のものを除いてすべてを忘れてしまいます。

(\_ x -> x)の人間が判読できる名前は、最初の引数を無視して2番目の引数を返すという事実を参照します。それをsecondArgとしましょう。

foldl1 (\_ x -> x) [1..4] 
= let secondArg = (\_ x -> x) in foldl secondArg 1 [2..4] 
= foldl (1 `secondArg` 2) [3..4] 
= foldl ((1 `secondArg` 2) `secondArg` 3) [4] 
= foldl (((1 `secondArg` 2) `secondArg` 3) `secondArg` 4) [] 
= (((1 `secondArg` 2) `secondArg` 3) `secondArg` 4) 
= 4