export toDescList from Data.Map

[Benedikt Huber]

Hi,

Scott Dillard schrieb:
> 
>  - I'm not sure what Benedikt Huber meant by 'view', but I think he 
> means exposing the tree structure, in a read-only way, to users. I think 
> its a shame that the Map/Set libraries do not expose this. The simplest 
> solution would be to have toTree functions that convert it to a 
> Data.Tree, but I don't think anybody actually likes that data type. A 
> specialized binary tree data type would be more elegant, but there is an 
> issue of how data is stored in the tree. Map/Set store keys and values 
> in internal nodes and use null leaves. IntMap/IntSet store all 
> keys/values in non-null leaves. So maybe this TreeView type would have 
> to be specific to either Map or IntMap. The idea here is that the 
> algorithms and data structures used for these trees are well-known. The 
> papers are linked from the documentation. So the library should expose 
> this to users, in a safe way.

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.

Supporting toTree (e.g. using a binary tree as you suggested) would be 
great as well, but I think T (k,v) does not need to be build an 
intermediate representation for supporting queries/folds, so a newtype 
should do as well.

>  - Since someone raised the issue of test suites for performance and 
> correctness, I think it would also be interesting to investigate what 
> effect the strictness annotations in the tree constructors have on 
> performance. 
 > ...
 > http://www.haskell.org/pipermail/libraries/2008-August/010371.html

Did you also measure the effect of removing strictness annotations  on 
space performance ?

> For my $0.02 your proposal is good. toDescList is very important to have 
> in many situations. I've had it un-hidden locally for a while now. It's 
> silly that it wasn't exported in the first place.
+1 for toDescList
foldrWithKey is certainly useful as well, but I think one should also 
think about monadic folds (and the other stuff from Data.Foldable), as 
explained above.

benedikt