Libraries Digest, Vol 61, Issue 23
sedillard at ucdavis.edu
Fri Sep 26 14:27:40 EDT 2008
> 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.
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
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries