Map Maker, Map Maker, Make Me a Map!

Shhhh ... I have a secret.

While I've been digging deep into the innards of MarkLogic's XQuery implementation I've accidentally fallen in love with something that's not quite a part of XQuery. It's a magical little object called a Map.

This map is not the one with roads and rivers and names and political boundaries. Instead, it's something that should be familiar to programmers in most other languages: a hash table. Like such objects elsewhere, this hash map can prove to be a remarkably useful instrument for an XQuery developer.

A map is not an XML structure (though internally it may very well be represented this way). Instead, with a map, you are able to use a key to hold an object - a simple type, an XML document, a sequence, another map or even a binary entity. You can then retrieve that object by passing the key to the map. As a very simple (and not terribly useful) example, suppose that you wanted to build a "Hello World" type application using a map. It would look something very similar to this in XQuery:

let $map := map:map()
return (
    map:put($map,"greeting","Hello"),
    map:put($map,"person","World"),
    fn:concat(map:get($map,"greeting"),", ",map:get($map,"person"),"!")
    )

The statement let $map := map:map() creates a map object, and assigns it to a variable $map. The map:get() statement retrieves from the map the value associated with the given key, while map:put() assigns a value to a given key. Any given map object can have a large number of such properties.

To put things into perspective, the code is nearly identical to the following code in Javascript:

var $map = new Object();
$map["greeting"] = "Hello";
$map["person"] = "World";
print($map["greeting"]+", "+$map["person"]+"!");

Put another way, a map is to XQuery what an Object is in JavaScript, and has a lot of the same capabilities. In the example given able, the map is overkill, but there are many places where maps are remarkably useful. One of the more common uses of such maps is as a way of accumulating content in a loop where you have to retain previous state of a situation. For instance, consider the word-frequence function given below:

declare function local:word-frequency($str as xs:string) as node(){
      let $str := fn:translate(fn:lower-case($str),",;.!?_","")
      let $tokens := fn:tokenize($str,' ')
      let $map := map:map()
      let $map-update := (for $token in $tokens return (map:put($map, $token, if (fn:index-of(map:keys($map),$token)) 
      then map:get($map, $token) + 1 else 1)))
      let $keys := map:keys($map)
       let $freq-words := for $key in $keys order by $key ascending return
                 (mapper:put($map,"_counts_",(map:get($map,"_counts_"),map:get($map,$key))),
                  <word count="{map:get($map,$key)}">{$key}</word>)
         let $freq-words-by-count := for $word in $freq-words order by fn:number($word/@count) descending return $word
      return
      <frequencies>
            <byword>{$freq-words}</byword>
             <bycount>{$freq-words-by-count}</bycount>
      </frequencies>
      };

This is an example that could have been done with XQuery using recursion, but it would have been difficult. It makes use of another function, the map:keys() function, which returns a list of all of the keys that the map itself contains as a sequence. For the given text it generates the following output:

<frequencies>
    <byword>
        <word count="2">a</word>
        <word count="2">best</word>
        <word count="4">it</word>
        <word count="2">men's</word>
        <word count="3">of</word>
        <word count="2">souls</word>
        <word count="3">the</word>
        <word count="2">time</word>
        <word count="3">times</word>
        <word count="2">to</word>
        <word count="2">try</word>
        <word count="4">was</word>
        <word count="2">worst</word>
    </byword>
    <bycount>
        <word count="4">it</word>
        <word count="4">was</word>
        <word count="3">of</word>
        <word count="3">the</word>
        <word count="3">times</word>
        <word count="2">a</word>
        <word count="2">best</word>
        <word count="2">men's</word>
        <word count="2">souls</word>
        <word count="2">time</word>
        <word count="2">to</word>
        <word count="2">try</word>
        <word count="2">worst</word>
    </bycount>
</frequencies>
</blockcodde>
 
It also uses two rather powerful patterns:
 
<blockcode>map:put($map, $key, (map:get($map, $key), $value))

and

 (map:put($map, $key, if (fn:index-of(map:keys($map),$key)) 
      then map:get($map, $key) + 1 else 1))

The first pattern, what I call a map sequencer, gets a sequence (possibly empty) stored in a map via a key, adds a new item to the sequence and stores the new sequence back into the same key value. This creates a persistent sequence which can be good for keeping track of state over the course of a number of operations.

The second routine implements a counter tied to a given key. This initializes the value for that map to 0 if it doesn't otherwise exist, adds one to that key, then persists it back to the key in the map. These patterns are useful enough to encode as separate functions - mapper:push() and mapper:acc() (for accumulate) in a "mapper" module.

module namespace mapper = "http://www.xmltoday.org/xmlns/mapper";
 
declare function mapper:push($map as item() ,$key as xs:string, $value as item()) {
    (map:put($map, $key, (map:get($map, $key), $value)))
};
 
declare function mapper:acc($map as item() ,$key as xs:string){
    (map:put($map, $key, if (fn:index-of(map:keys($map),$key)) 
      then map:get($map, $key) + 1 else 1))
};

This module can then be used to simplify the frequency function, as follows:

declare function local:word-frequency($str as xs:string) as node(){
      let $str := fn:translate(fn:lower-case($str),",;.!?_","")
      let $tokens := fn:tokenize($str,' ')
      let $map := map:map()
      let $map-update := (for $token in $tokens return mapper:acc($map,$token))
      let $keys := map:keys($map)
       let $freq-words := for $key in $keys order by $key ascending return
                 (mapper:push($map,"_counts_",map:get($map,$key)),
                  <word count="{map:get($map,$key)}">{$key}</word>)
         let $freq-words-by-count := for $word in $freq-words order by fn:number($word/@count) descending return $word
      return
      <frequencies>
            <byword>{$freq-words}</byword>
             <bycount>{$freq-words-by-count}</bycount>
      </frequencies>
      };

It should be noted here that in most cases it is possible to use other XQuery structures to perform most map-like functions, but such code can be byzantine to write and maintain. Moreover, maps introduce side-effects into your XQuery code, which can in certain instances make such code more error-prone. However, their utility is such that, used properly, they can solve a number of problems that are otherwise difficult to do in more "traditional" ways.