haskell - foldr和foldl之间的区别对 map 和集合重要吗？

(与Haskell相比，此问题的适用范围更广，但这是我要用的语言。)
foldl和foldr之间的区别似乎取决于列表是有序的。也就是说，foldl和foldl通过将函数应用于起始值和第一个或最后一个元素，然后将其应用于第一个应用程序的结果以及第二个或倒数第二个元素，然后对第二个应用程序的结果进行折叠来折叠列表到第三个或倒数第二个元素，等等。

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

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.

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

最佳答案

如果引用 Data.Set 或 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

和Set的 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

在上面的树上应用foldl (+) 0时，以左，当前，右的顺序，给出:

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

它显示与Set等效的Set的foldr和foldl适用于该列表，如下所示:

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是否表现为列表？ (我想答案是肯定的，您可以自己检查一下)

否，如上面所示的源代码:

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

和

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

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

关于haskell - foldr和foldl之间的区别对 map 和集合重要吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53678079/