[xquery-talk] map module for XQUERY ?

John Snelson john.snelson at marklogic.com
Wed Nov 20 01:53:26 PST 2013

The following libraries are written in pure XQuery 3.0:

rbtree.xq - https://github.com/jpcs/rbtree.xq

Functional implementation of a red/black tree (ordered set) that allows 
a custom implementation of the comparison function. See the included 
"map.xq" for how this can be used to implement a map data structure 
using "lt" comparison. Should be easy to implement an alternative map 
that allows node keys with a suitable comparison function.

hamt.xq - https://github.com/jpcs/hamt.xq

Functional implementation of a hash array mapped trie (hash set) that 
allows a custom hash function and equality function. See the included 
"hashmap.xq" for how this can be used to implement a map data structure.

Hope that helps,


On 20/11/13 09:43, jean-marc Mercier wrote:
> Hello,
> I am looking for a map module in XQUERY that would have the following
> behavior. Does somebody ever heard of such a module ?
> 1) The default behavior for inserting keys should be using the
> fn:distinct-values(). Note that map module using this mechanism already
> exists, see for instance BaseX map:module :
> http://docs.basex.org/wiki/Map_Module
> 2) Accept functions as values. Why this could be useful ? Well, it is
> really useful for a lot of things. The first very useful things would be
> to use this functionality to bind external parameters to functions.
> For instance I could write, (useful for the point 3) below)
> declare function
> local:is_data1_smaller_than_data2($data1,$data2,$map_bindings){
>        map:get($map_bindings,"less")($data1,$data2)
> };
> 3) Accept an optional, external ordering predicate. This is actually
> what is done with every structured languages. For instance, set in C++
> (that are indeed maps) are defined as
> template < class T,                        // set::key_type/value_type
>             */_class Compare = less<T>_/*,        // set::key_compare/value_compare
>             class Alloc = allocator<T> >    // set::allocator_type
>             > class set;
> where the ordering predicate is optional (*/_class Compare = less<T>).
> _/*Why having an optional ordering predicate could be useful in ?
> Because of point 4) below : to use node() as keys in map.
> 4) Accept node() as keys. This is very useful to a lot of things.
> However, it does not exists a canonical ordering for nodes. The function
> deep-equal() could be a candidate, but it does not define an ordering,
> and performances in insertion using this function would be tremendous.
> Thus, to accept node() as keys for maps, one need first to provide an
> external ordering predicate for nodes, see point 3) above.

John Snelson, Lead Engineer                    http://twitter.com/jpcs
MarkLogic Corporation                         http://www.marklogic.com

More information about the talk mailing list