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

[Mike Izbicki]

I've got a Partitionable class that I've been using for this purpose:

https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/ConstraintKinds/Partitionable.hs

The function called "parallel" in the HLearn library will automatically
parallelize any homomorphism from a Partionable to a Monoid.  I
specifically use that to parallelize machine learning algorithms.

I have two thoughts for better abstractions:

1)  This Partitionable class is essentially a comonoid.  By reversing the
arrows of mappend, we get:

comappend :: a -> (a,a)

By itself, this works well if the number of processors you have is a power
of two, but it needs some more fanciness to get things balanced properly
for other numbers of processors.  I bet there's another algebraic structure
that would capture these other cases, but I'm not sure what it is.

2) I'm working with parallelizing tree structures right now (kd-trees,
cover trees, oct-trees, etc.).  The real problem is not splitting the
number of data points equally (this is easy), but splitting the amount of
work equally.  Some points take longer to process than others, and this
cannot be determined in advance.  Therefore, an equal split of the data
points can result in one processor getting 25% of the work load, and the
second processor getting 75%.  Some sort of lazy Partitionable class that
was aware of processor loads and didn't split data points until they were
needed would be ideal for this scenario.

On Sat, Sep 28, 2013 at 6:46 PM, adam vogt <vogt.adam at gmail.com> wrote:

> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130929/736cf2c3/attachment.htm>