Почему нет метода сгиба?

Question

Я заметил, что класс Foldable содержит fold, foldl, foldr, foldl 'и foldr', но нет сгиба ' (для строгих моноидальных складок)

Как я могу эмулировать поведение сворачивания с помощью IntMap (который реализован в виде дерева, но не дает прямого доступа к внутренним узлам).

---

Мотивация:

В частности, если у меня есть IntMap, содержащий M IntMap размера K (с общим размером N = M*K), я бы хотел объединить их во время выполнения O(N * log(M)) big-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)). Поэтому у меня больше нет мотивации для этого вопроса.

Answer 1

Так как я не мог найти библиотеку с полным Foldablefold'Чтобы получить ответ на основной вопрос, я написал код для предложения @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