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的状态机.想象一下因为来自-RIGHT的pacman而在中缀表示法中.

foldl(foldLEFT)从-LEFT执行相同的操作,但是用中缀表示法编写的转换函数从右边获取其输入参数.因此机器从左端开始使用列表.吃豆子消耗从-LEFT列表张开嘴向右,因为口(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]