CODEWITHSUNDEEP
haskellbig-olazy-evaluationfoldmonoids
dspyz
dspyz

Reputation: 5500

Why is there no fold' method?

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

How can I emulate the behavior of fold' with an IntMap (which is implemented as a tree, but doesn't give direct access to the internal nodes).

Motivation:

In particular, if I have an IntMap containing M IntMap's of size K (with total size N = M*K), I'd like to union them in O(N * log(M)) big-O running time. Something like:

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

This would work because IntMap is an instance of Monoid with mappend defined as union. Note that in general, using foldl' or foldr' is theoretically slower since it requires Omega(N * log N) worst-case running time. Admittedly, this is probably an insignificant difference in practice, but I'm pedantic enough to care about theoretically optimal bounds

Oops, the above is wrong. I went over it more carefully and now I realize it doesn't matter whether you use fold or foldl or foldr, the running time will be in O(N * log(M)). So I no longer have any motivation for this question.

Upvotes: 4

Views: 192

Answers (1)

Ørjan Johansen
Ørjan Johansen

Reputation: 18189

Since I couldn't find any library with the full Foldable fold', to have an answer to the basic question, I wrote up some code for @Carl's suggestion from the comments above (WHNF only):

{-# 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

Upvotes: 3

Related Questions