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

Question

(这个问题比 Haskell 更普遍，但这是我用来陈述它的语言。)
foldl的区别和 foldr似乎取决于列表是有序的这一事实。即，foldl和 foldl通过将函数应用于起始值和第一个或最后一个元素，然后应用于第一个应用程序的结果和第二个或倒数第二个元素，然后将第二个应用程序的结果应用于第三个或第三个元素来折叠列表 - to-last 元素等

但是 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 和集合没有排序。我应该期待 foldl 版本之间的性能差异吗？和 foldr为集合和映射定义，或者 foldr f做与 foldl (flip f) 完全相同的事情?

Answer 1

实际上，集合和 map 是有序的。这就是为什么所有的 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但实际上有两种不同的类型，这表明排序确实很重要。