export toDescList from Data.Map
benjovi at gmx.net
Fri Sep 26 10:12:17 EDT 2008
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
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
More information about the Libraries