Haskell - foldl和foldr?

问题描述 投票:48回答:1

foldlfoldr之间的差异只是循环的方向吗?我认为他们做了什么,而不仅仅是朝这个方向有所不同?

haskell fold
1个回答
101
投票

如果你的函数不是关联的(即,你将表达式括在哪个方面很重要),那就有区别了,例如, foldr (-) 0 [1..10] = -5foldl (-) 0 [1..10] = -55。 在一个小规模,这是因为10-(20-(30))((10)-20)-30不同。

而因为(+)是关联的(无论你添加子表达式的顺序如何), foldr (+) 0 [1..10] = 55foldl (+) 0 [1..10] = 55(++)是另一个联合操作,因为xs ++ (ys ++ zs)给出了与(xs ++ ys) ++ zs相同的答案(虽然第一个更快 - 不要使用foldl (++)

有些功能只能以一种方式工作: foldr (:) :: [a] -> [a] -> [a]但是foldl (:)是无稽之谈。

看看Cale Gibbard的图表(来自wikipedia article);你可以看到用真正不同的数据对调用f

另一个不同之处在于因为它匹配列表的结构,所以foldr通常对于惰性求值更有效,所以只要f在其第二个参数(如(:)(++))中是非严格的,就可以使用无限列表。 foldl很少是更好的选择。如果你正在使用foldl它通常值得使用foldl'因为它是严格的并且阻止你建立一长串的中间结果。 (关于this question答案中有关此主题的更多信息。)

© www.soinside.com 2019 - 2024. All rights reserved.