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
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
Did you also measure the effect of removing strictness annotations on space performance ? think about monadic folds (and the other stuff from Data.Foldable), as explained above. benedikt