Date: Fri, 26 Sep 2008 15:36:46 +0100 From: Ross Paterson

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