foldr和foldl进一步的解释和示例

Question

我看了看 不同的折叠 和 一般折叠 以及其他一些，他们很好地解释了这一点。

在这种情况下，我仍然在Lambda如何工作时遇到麻烦。

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

有人可以逐步经历那个尝试向我解释吗？

以及如何 foldl 工作？

Answer 1

使用

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 2

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在infix符号中的f，因为pacman从右翼出现。

foldl（foldleft）从左左右执行相同的操作，但是用infix符号编写的过渡函数从正确地获取其输入参数。因此，机器从左端开始消耗列表。 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' (+) 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）''''）），内存））））之后都会对其进行评估。

第三个就像第二个，但有另一个公式。

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

infix符号在这里可能会更清楚。

让我们从定义开始：

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]