haskell FOLDR和FOLDL进一步的解释和例子

7ajki6be  于 2022-11-14  发布在  其他
关注(0)|答案(6)|浏览(166)

我已经看过different foldsfolding in general以及其他几个,他们解释得相当好。
在这种情况下,我仍然不知道lambda是如何工作的。

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

有人能一步一步地给我解释一下吗?
还有foldl是如何工作的?

js5cn81o

js5cn81o1#

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)做同样的from-LEFT,但是转换函数是用中缀符号写的,它的输入参数是从右开始的,所以机器从左端开始消费列表。Pacman消费from-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)+...)浪费内存,然后计算所有公式。
第三个和第二个一样,但是用了另一个公式。

jdgnovmf

jdgnovmf2#

使用中

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

还有

k y ys = ys ++ [y]

让我们打开 Package :

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]
h9vpoimq

h9vpoimq3#

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]
ecbunoof

ecbunoof4#

中缀符号在这里可能会更清楚。
让我们从定义开始:

foldr f z []     = z
foldr f z (x:xs) = x `f` (foldr f z xs)

为了简洁起见,我们将(\y ys -> ys ++ [y])写成g。下面几行是等效的:

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]
dsekswqp

dsekswqp5#

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

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

其次,foldl从列表的最左边或第一个元素开始,而foldr从列表的最右边或最后一个元素开始,这在上面并不明显,因为列表只有一个元素。
我的记忆术是这样的:leftright描述了两件事:

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

ffdz8vbo6#

我倾向于用运动来记忆事物,所以我想象并形象化价值在周围飞舞。这是我对foldl和foldr的内在表征。
下图执行了几项操作:
1.以一种直观的方式命名折叠函数的参数(对我来说),
1.示出了每个特定折叠从哪一端开始工作(fold1从左边开始,foldr从右边开始),
1.对累加器和当前值进行颜色编码,
1.通过lambda函数跟踪值,将它们Map到折叠的下一次迭代。
我记得foldl的参数是按字母顺序排列的(\a c ->),而foldr的参数是按相反的字母顺序排列的(\c a ->),l表示从左边取,r表示从右边取。

相关问题