15

我看过不同的折叠和一般折叠以及其他一些折叠，他们解释得很好。

在这种情况下，我仍然无法确定 lambda 的工作方式。

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

有人可以一步一步地向我解释吗？

还有如何foldl工作？

4

5 回答 5

35

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 想象为来自-RIGHT 的 pacman。

foldl (foldLEFT) 从左到右执行相同的操作，但是以中缀表示法编写的转换函数从右获取其输入参数。所以机器从左端开始消费列表。Pacman 使用从左到右的嘴巴来消费列表，因为嘴巴是 (b->a->b) 而不是 (a->b->b)。

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

第一个 - 逐步 - 创建列表的一个条目，评估它并使用它。

第二个首先创建一个很长的公式，用 ((...((0+1)+2)+3)+...) 浪费内存，然后计算所有的。

第三个类似于第二个，但使用了另一个公式。

于 2010-10-16T21:16:46.820 回答
15

使用

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]
于 2010-10-16T20:02:58.293 回答
6

的定义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]
于 2010-10-16T20:00:41.243 回答
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]
于 2010-10-16T20:11:25.090 回答
0

我首先记住这一点的方法是使用关联敏感 减法运算：

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

其次，foldl从列表的最左边或第一个元素开始，而foldr从列表的最右边或最后一个元素开始。上面并不明显，因为列表只有一个元素。

我的记忆是这样的：leftorright描述了两件事：

  • 减号 ( -) 符号的位置
  • 列表的起始元素
于 2021-03-06T05:08:57.797 回答