haskell - 为什么没有 fold' 方法？

我注意到可折叠类包含 fold、foldl、foldr、foldl' 和 foldr'，但没有 fold'(对于严格的幺半群折叠)

如何使用 IntMap 模拟 fold' 的行为(实现为树，但不提供对内部节点的直接访问)。

动机:

特别是，如果我有一个包含大小为 K 的 M IntMap(总大小 N = M*K)的 IntMap，我想在 O(N * log(M)) 大 O 运行时间中将它们联合起来。就像是:

unionMaps :: IntMap (IntMap a) -> IntMap a
unionMaps = fold'

这是可行的，因为 IntMap 是 Monoid 的一个实例，其中 mappend 定义为 union。请注意，一般而言，使用 foldl' 或 foldr' 理论上较慢，因为它需要 Omega(N * log N) 最坏情况运行时间。诚然，这在实践中可能是微不足道的差异，但我足够学究到关心理论上的最佳界限

哎呀，上面写错了。我更仔细地检查了它，现在我意识到使用 fold 或 foldl 或 foldr 并不重要，运行时间将在 O(N * log(M)) 中。所以我对这个问题不再有任何动力。

最佳答案

由于我找不到任何包含完整 Foldable fold' 的库，为了回答基本问题，我从上面的评论中为@Carl 的建议编写了一些代码(仅限 WHNF):

{-# LANGUAGE BangPatterns #-}
import Data.Monoid
import Data.Foldable

newtype StrictM m = StrictM { getStrict :: m }

instance Monoid m => Monoid (StrictM m) where
    mempty = StrictM mempty
    mappend (StrictM !x) (StrictM !y) = StrictM (mappend x y)

fold' :: (Foldable t, Monoid m) => t m -> m
fold' = getStrict . foldMap StrictM

关于haskell - 为什么没有 fold' 方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24251951/

intMap

haskell - 为什么没有 fold' 方法？