[xquery-talk] map module for XQUERY ?

[Christian Grün]

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