5

我正在阅读 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'and tail'。

我的理解是二进制函数应该依次应用于累加器和列表中的每个元素，从而遍历所有列表。为什么这会停在头部（或尾部）？

我理解_（下划线）的意思是“随便”或“我不在乎”，但是这如何停止遍历所有列表？

4

2 回答 2

8

foldr 结合了两个项目 - 当前的“运行总计”项目和新项目。

(\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
于 2013-05-21T20:06:38.567 回答
6

我们先看一下foldr1first的定义：

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 : [])，因此——希望这能回答你的问题——递归在我们处理完列表的其余部分之前停止。

于 2013-05-21T20:20:49.187 回答