Date: Fri, 26 Sep 2008 15:36:46 +0100
From: Ross Paterson <ross@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