LeoWoerteler/basex — Issue #5: Implement XQuery Sequences as Finger Trees
Author: LeoWoerteler
Created: 2012-02-20 16:11:04+00:00
State: open

Currently BaseX implements XQuery sequences as lightweight array lists, which is fast for simple use cases, but breaks down completely when sequences are used as immutable lists because of the copying overhead.

Example:
------------

The standard XQuery function `fn:map($f, $xs)` applies the function `$f` so all elements of the sequence `$xs`, concatenating the results. Implementing it in XQuery is straight-forward:

```xquery
declare function local:map(
$f as function(item()) as item()*,
$xs as item()*
) as item()* {
if(empty($xs)) then ()
else (
$f(fn:head($xs)),
local:map($f, fn:tail($xs))
)
};
```

Unfortunately the function performs very poorly, as the result sequence has to be copied in every recursive call, which leads to an *O(n²)* runtime (with *n* being the length of the list).

Finger Trees
-----------------

[Finger trees](http://en.wikipedia.org/wiki/Finger_tree) are an immutable, purely functional data structure with properties nicely fitting this use case:

* `cons`, `reverse`, `tail`: amortized *O(1)*
* `append` and `split`: *O(log n)*

Even if should not be replaced by finger trees, an option to turn them on would be nice for idiomatic functional XQuery code.