foldr 和 foldl 之间的区别对于地图和集合是否重要？

Question

（这个问题比 Haskell 更普遍，但这是我用来陈述它的语言。）

foldl 和 foldr 之间的区别似乎取决于列表是有序的。也就是说，foldl 和 foldl 通过将函数应用于起始值和第一个或最后一个元素，然后应用于第一个应用程序的结果和第二个或倒数第二个元素来折叠列表，然后第二次应用到第三个或倒数第三个元素的结果，依此类推

但是 Haskell 的 Data.Set 和 Data.Map 库定义了它们自己的 foldl 和 foldr 版本。例如，对于地图，它们是：

foldr :: (a -> b -> b) -> b -> Map k a -> b
foldl :: (b -> a -> b) -> b -> Map k a -> b -- I've swapped `a` and `b`
  -- in the second type signature to clarify the correspondence.

地图和布景未排序。我是否应该期望为集合和地图定义的 foldl 和 foldr 版本之间的性能差异，或者 foldr f 是否与 foldl (flip f) 做完全相同的事情？

Answer 1

实际上，集合和映射是有序的。这就是为什么所有 set 和 map 函数对键类型都有 Ord 约束。它们按元素类型的自然顺序自动排序。因此，如果您的集合包含 {3, 5, 2, 1, 4}，那么 Haskell 将按照 {1, 2, 3, 4, 5}.

的顺序看到它（出于折叠目的）

但是让我们暂时忘掉它。假设我们处在一个数据真正无序的完美世界中。即便如此，foldl 和 foldr 之间的差异还是很大的。假设我有之前的集合：{3, 5, 2, 1, 4}，我想对其执行一些操作.*。

foldl (.*) 0 mySet = ((((0 .* 3) .* 5) .* 2) .* 1) .* 4
foldr (.*) 0 mySet = 3 .* (5 .* (2 .* (1 .* (4 .* 0))))

因此，即使操作恰好是关联的，初始元素也会放在 foldl 与 foldr 的对面。事实上，有些操作 甚至不会工作 如果使用错误的折叠实现。考虑 toList，它在 Data.Foldable 中定义，可用于任何 Foldable 对象（包括列表、映射和集合）。一种可能的实现是

toList :: Foldable t => t a -> [a]
toList = foldr (:) []

如果我们尝试做一个 foldl

definitelyWrong :: Foldable t => t a -> [a]
definitelyWrong = foldl (:) []

然后它甚至没有编译。

wrongfold.hs:5:25: error:
    • Occurs check: cannot construct the infinite type: a ~ [a]
      Expected type: [a] -> [a] -> [a]
        Actual type: a -> [a] -> [a]

这是因为折叠的关联方式不同，甚至可以使用采用两个不同类型参数的累加操作，这从两者的类型签名中也很明显

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

请注意第一个参数不是 a -> a -> a 但实际上有两种不同的类型，这表明顺序确实很重要。

Answer 2

Maps and sets aren't ordered. Should I expect performance differences between the versions of foldl and foldr defined for sets and maps

如果你参考Data.Set or Data.Map的源代码，你会发现它们的元素是用二叉树组织的：

data Map k a  = Bin !Size !k a !(Map k a) !(Map k a)
              | Tip 

data Set a    = Bin !Size !a !(Set a) !(Set a)
              | Tip

和集合的foldr：

foldr f z = go z
  where
    go z' Tip           = z'
    go z' (Bin _ x l r) = go (f x (go z' r)) l

使用深度优先搜索以 右、当前、左 顺序遍历树，因此当 foldr (+) 0 申请跟随树时：

给予，

4 + (1 + (2 + (3 + 0)))

和foldl

foldl f z = go z
  where
    go z' Tip           = z'
    go z' (Bin _ x l r) = go (f (go z' l) x) r

with order left, current, right 当应用 foldl (+) 0 到上面的树时，给出：

((((0 + 4) + 1) + 2) + 3)

它表明 foldr 和 foldl 的 Set 等效于应用于列表：

foldr (+) 0 [4, 1, 2, 3] = 4 + (1 + (2 + (3 + 0)))
foldl (+) 0 [4, 1, 2, 3] = ((((0 + 4) + 1) + 2) + 3)

情况与Data.Map类似，此处不再赘述。

此外，正如我们所知，foldr可以应用于无限列表（但foldl不能），例如：

take 10 $ foldr ((:) . sum) [] $ chunksOf 3 [1..] = [6,15,24,33,42,51,60,69,78,87]

（此处 chunksOf 将列表分组为 [[1,2,3], [4,5,6]...]）

但是如果树的路径是无限的，比如：

                   1
                  / \
                 4   2
                      \
                       3
                        \
                         ...  <- infinite path

Set 的 foldr 是否像上面提到的列表一样？（我猜答案是肯定的，你可以自己查）

does foldr f do exactly the same thing as foldl (flip f)?

否，如上图源码：

foldr          = ... go (f x (go z' r)) l

和

foldl (flip f) = ... go (f x (go z' l)) r

树的遍历顺序不同，但是foldr和foldl之间的通用关系可以在这个post中找到：Defining foldl in terms of文件夹

foldr 和 foldl 之间的区别对于地图和集合是否重要？

Is the distinction between foldr and foldl important for maps and sets?

haskell

fold

unordered