4

我注意到 Foldable 类包含 fold、foldl、foldr、foldl' 和 foldr'，但没有 fold'（对于严格的单曲面折叠）

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

动机：

特别是，如果我有一个包含 M 个大小为 K 的 IntMap 的 IntMap（总大小 N = M*K），我想在 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)) 中。所以我对这个问题不再有任何动机。

4

1 回答 1

3

由于我找不到任何完整的库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
于 2014-06-17T00:53:21.890 回答