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

[adam vogt]

On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton <rrnewton at gmail.com> 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