Foldr 和 Foldl 进一步解释和示例

Question

我查看了不同的折叠和一般折叠 以及其他一些内容，他们解释得相当好。

我仍然不知道 lambda 在这种情况下如何工作。

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 的状态机，从右端开始。想象一下中缀表示法中的 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)+...) 浪费内存，然后对所有公式进行求值。

第三个与第二个类似，但公式不同。

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 从列表的最右边或最后一个元素开始。上面这一点并不明显，因为列表只有一个元素。

我的助记符是这样的：left 或 right 描述了两件事：

• 减号 (-) 符号的位置
• 列表的起始元素

Answer 6

我倾向于通过运动来记住事物，所以我想象并想象飞来飞去的价值观。这是我对foldl 和foldr 的内部表示。

下图做了一些事情：

1. 以直观的方式命名折叠函数的参数（对我来说），
2. 显示每个特定折叠从哪一端开始工作（foldl 从左侧，foldr 从右侧），
3. 颜色编码累加器和当前值，
4. 通过 lambda 函数跟踪这些值，将它们映射到折叠的下一次迭代。

便于记忆的是，我记得foldl的参数按字母顺序排列（\ac ->），foldr的参数按相反的字母顺序排列（\ca ->）代码>）。 l 表示从左侧获取，r 表示从右侧获取。