On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton <rrnew...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe