Re: Maps in exslt2?

Hi Vladimir,

I think it's really important to get some good data structures into 
XQuery and XSLT 2.0. I've already written a read/black tree 
implementation in pure XQuery 1.1 (using 1st class function closures) 
which I was planning to release via EXPath when appropriate.

I designed my map interface like this:

declare function map:put(
   $map as function() as item()*?,
   $key as item(),
   $value as item()*
) as (function() as item()+)+

declare function map:get(
   $map as function() as item()*?,
   $key as item()
) as item()*

declare function map:contains(
   $map as function() as item()*?,
   $key as item()
) as xs:boolean

declare function map:fold(
   $f as function(item()*, item(), item()*) as item()*,
   $z as item()*,
   $map as function() as item()*?
) as item()*

It's a declarative, functional API, so putting an entry into a map 
creates a new map. The keys are singleton items, and the values are 
sequences. The map:fold() function visits each map entry executing $f 
and accumulating a result from it.

Looking at the API now, I'm thinking it probably needs map:remove() to 
remove an entry, and maybe map:keys() to return a sequence of all the 
keys in the map.

I'm also thinking about other useful functional data structures to 
implement using XQuery 1.1. I'll probably implement a finger tree at 
some point to use as an array/queue etc.

John

Vladimir Nesterovsky wrote:
>>> The suggestion has been declined (probably my arguments were 
>>> not convincing). 
>> You can probably assume that different people voted against it for 
> different
>> reasons. Some may have felt the arguments unconvincing; some may have 
> felt
>> that it was outside the scope of the 1.1/2.1 release (which some people
>> think is almost finished); ...
> 
> I can understand arguments of the WG. That is why I'm talking now of exslt, 
> 
> and is aiming to binary trees. As items in binary tree algorithms do not 
> play a role (they are just attached to the tree), implementation is 
> modular:
> 
> Interface for a tree itself includes functions to:
> create a tree (create, insert, remove);
> navigate subtree tree (like left, right, size of subtree);
> 
> Map is a tree, which assumes that items are key, value pairs. Thus 
> interface for the map extends tree with search, and create (create, insert, 
> 
> delete) according to a key.
> 
> Tree items should probably be expressed in terms of function items.
> The sample implements items as xml elements, which makes it inefficient (in 
> 
> xslt 2.1 implementation is efficient if one counts operation complexity).
> 
> But my point was to open a discussion and to show that things are not so 
> complicated and are very modular.
> 
> P.S. Sorry, if you got this message twice.
> --
> Vladimir Nesterovsky
> http://www.nesterovsky-bros.com/
> 
> _______________________________________________
> exslt mailing list
> [email protected]
> http://www.exslt.org/list

-- 
John Snelson, Oracle Corporation               http://twitter.com/jpcs
Berkeley DB XML:            http://oracle.com/database/berkeley-db/xml
XQilla:                                  http://xqilla.sourceforge.net