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对key类型有约束的原因.它们按元素类型的自然顺序自动排序.因此,如果你的集合包含{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

地图和套装未排序。我是否应该期望为集合和映射定义的 Foldl 和 Foldr 版本之间的性能差异

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

使用深度优先搜索以right、current、left的顺序遍历树，因此当foldr (+) 0应用于跟随树时：

                   1
                  / \
                 4   2
                      \
                       3

给出，

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)

它表明foldr和foldlof 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

of Set 的行为是否foldr如上面提到的 list 一样？（我想答案是肯定的，你可以自己查一下）

Foldr f 的功能与 Foldl (flip f) 的功能完全相同吗？

不是的，如上图源码：

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

和

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

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