Libraries Digest, Vol 61, Issue 23

[Scott Dillard]

> Date: Fri, 26 Sep 2008 15:36:46 +0100
> From: Ross Paterson <ross at soi.city.ac.uk>
>
> On Fri, Sep 26, 2008 at 04:12:17PM +0200, Benedikt Huber wrote:
> > I think that having a function
> >
> > > treeView :: Map k v -> T (k,v)
> >
> > s.t. T is an instance of Foldable, supports efficient left and right
> > folds, and additional operations like subrange queries (all pairs (k,v)
> > s.t. l <= k <= u) would be useful.
> > I'd like to have all functions from Data.Foldable available for folds
> > with key, e.g fold[lr]MWithKey.
>
> Map has split and splitLookup for subrange queries, and you could get
> the folds with
>
>        mapWithKey (,) :: Map k v -> Map k (k,v)
>
>
I don't follow FP research, but has anyone formalized the "divide and
conquer" strategy into a type class? I guess it would be something like
MapReduce, but I don't know what the details of that framework are.
Something like...

class DivideAndConquer t where
  mapReduce :: (a -> b) -> (b -> b -> b) -> t a -> b

splitLookup can get you close, but the user does not know a good split
position, so he has to guess something like halfway between min and max. I
think in a many-core setting this would be a heavily used method. Data.Map
and Data.Sequence would be very good at implementing it because they are
balanced, but Data.Tree and Data.IntMap can also do it, just not with good
load-balancing guarantees.

The other option, related to this thread, is to just have a BinTree data
type, like Data.Tree but strictly binary, and have the various balanced-tree
libraries provide views of that type. Then one needs to write mapReduce for
only one data type.

Scott
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20080926/6646d781/attachment.htm