为什么这些褶皱停在头/尾？

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

折叠器结合了两个项目 - 当前"运行总计"类别的项目和新项目.

(\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)将引用它忽略其第一个参数并返回其第二个参数的事实.我们称之为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

Answer 2

我们来看看foldr1第一个的定义:

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

然后,考虑调用你的函数head',

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

列表,比方说[2, 3, 5]:

head' [2, 3, 5]

现在,填写右侧head'给出

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

回想一下,这[2, 3, 5]是语法糖(2 : 3 : 5 : []).所以,定义的第二种情况foldr1适用并且我们屈服

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

现在,减少应用程序会导致2绑定x并foldr1 (\x _ -> x) (3 : 5 : [])绑定到被忽略的参数_.剩下的是lambda抽象的右侧,x取而代之的是2:

2

请注意,延迟评估会使被忽略的参数foldr1 (\x _ -> x) (3 : 5 : [])保持未评估状态,因此希望能够回答您的问题 - 在我们处理列表的其余部分之前,递归会停止.