[xquery-talk] map module for XQUERY ?

[John Snelson]

On 03/12/13 12:17, jean-marc Mercier wrote:
>  > You can create a simple linked list using a cons cell:
>
> @John : Right, but you will always have quadratic complexity in length
> creating the sequence $seq.

Not always. But that was just example code - don't create it from a 
sequence.

>  >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?
>
> @ Christian. Indeed, I realized after profiling my rewriting of John
> code that its code implementation has also a quadratic complexity in
> sequence length. John, as I, need at a point to allocate memory for
> writing this tree implementation. If we want to stay pure xquery, this
> will be done with quadratic complexity in length, at least I can't see
> any work around to that.

My red/black tree implementation only ever uses sequences of length 4, 
which will therefore have a constant cost to create (in the size of the 
red/black tree).

John

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