Why is there no folding method?

Question

I noticed that the Foldable class contains fold, foldl, foldr, foldl 'and foldr', but no fold '(for strict monoidal folds)

How can I emulate fold 'behavior with IntMap (which is implemented as a tree but does not give direct access to internal nodes).

---

<s> Motivation:

In particular, if I have an IntMap containing M IntMap of size K (with a total size of N = M * K), I would like to combine them into O (N * log (M)) Big-O runtimes, Something like :

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

This will work because IntMap is a Monoid instance with mappend defined as union. Note that in the general case, using foldl 'or foldr' is theoretically slower as it requires the worst Omega (N * log N) run time. Admittedly, this is probably a slight difference in practice, but I'm pedantic enough to care about the theoretically optimal boundaries C>

---

Unfortunately, this is not true. I carefully studied it, and now I understand that it does not matter whether you use a fold or fold or foldr, the runtime will be in O (N * log (M)). Therefore, I no longer have the motivation for this question.

Answer 1

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