Re: [Haskell-cafe] What class for splittable data / balanced-fold?

On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton wrote:

Hi all,

We all know and love Data.Foldable and are familiar with left folds and right folds. But what you want in a parallel program is a balanced fold over a tree. Fortunately, many of our datatypes (Sets, Maps) actually ARE balanced trees. Hmm, but how do we expose that?

Hi Ryan, At least for Data.Map, the Foldable instance seems to have a reasonably balanced fold called fold (or foldMap):

fold t = go t where go (Bin _ _ v l r) = go l `mappend` (v `mappend` go r)

This doesn't seem to be guaranteed though. For example ghc's derived instance writes the foldr only, so fold would be right-associated for a:

data T a = B (T a) (T a) | L a deriving (Foldable)

Regards, Adam