Hi Jean-Marc, > To report over this topic, I've written in XQUERY a Map that have the > desired properties, rewriting John Snelson rbtree.xq > - It can handle nodes or functions as keys, if of course the user provides > its external ordering function, this point being left under the user > responsibility. > - It can remove nodes. > > However, it suffers from performance issues : creating a map is quadratic > (n^2) in map length (n), to be compared to n log_2(n) complexity for a > normal red / black tree insertion.
I can only speculate, because we haven’t seen your implementation, but I am wondering why you didn’t take advantage of John’s existing $lessthan function argument in order to compare all kinds of items? > Maps (even immutable ones like Phil's Bagwell) are indeed implemented > using stacks as far as I know. When talking about stacks, do you refer to dynamic arrays (which are downsized when entries are deleted)? There are lots of ways how you can implement maps. On a low level, it’s possible to store all kinds of data structures in arrays (on machine level, it’s the only choice you have), but that’s the imperative way of thinking. The functional language paradigm is completely different: here, you live in an immutable world which does not allow you to modify existing data. However, the existence of immutable maps, finger trees or John’s tree demonstrates on the one hand that it’s possible to build efficient data structures with functional languages and, on the other hand, that conventional maps and arrays will not cover the requirements of functional languages. Maybe the most important thing here is: It takes *time* to get into the functional way of thinking (Okasaki’s book on Functional Data Structures may a good start). If you prefer more straightforward solutions, or if you really want to get 100% performance, a functional language may not be the best tool (well, some people may object..). Christian _______________________________________________ [email protected] http://x-query.com/mailman/listinfo/talk
