<div dir="ltr"><br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Date: Fri, 26 Sep 2008 15:36:46 +0100<br>
From: Ross Paterson <<a href="mailto:ross@soi.city.ac.uk">ross@soi.city.ac.uk</a>><br>
<br>
On Fri, Sep 26, 2008 at 04:12:17PM +0200, Benedikt Huber wrote:<br>
> I think that having a function<br>
><br>
> > treeView :: Map k v -> T (k,v)<br>
><br>
> s.t. T is an instance of Foldable, supports efficient left and right<br>
> folds, and additional operations like subrange queries (all pairs (k,v)<br>
> s.t. l <= k <= u) would be useful.<br>
> I'd like to have all functions from Data.Foldable available for folds<br>
> with key, e.g fold[lr]MWithKey.<br>
<br>
Map has split and splitLookup for subrange queries, and you could get<br>
the folds with<br>
<br>
mapWithKey (,) :: Map k v -> Map k (k,v)<br>
<br>
</blockquote></div><br>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...<br>
<br>class DivideAndConquer t where<br> mapReduce :: (a -> b) -> (b -> b -> b) -> t a -> b<br><br>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.<br>
<br>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. <br>
<br>Scott<br><br></div>