Higher-Order XQuery Modules

This repository contains various algorithms and data structures implemented in pure XQuery 3.0. They all are purely functional and mostly inspired by Chris Okasaki's excellent Purely Functional Data Structures and similar modules written in Haskell.

Some examples are:

• a priority queue implemented as a Skew Heap
• a map implemented as a Red-Black Tree (or alternatively as an AVL Tree)
• a FIFO queue implemented as a pair of linked lists

An example application that uses all of the above under the hood is Dijkstra's single-source shortest path algorithm.

Data Types

Data types are mostly encoded as inline functions using the Scott Encoding. This means that arbitrary sequences can be stored and retrieved without the need for serialization.

Documentation

Functions and variables are annotated with xqDoc comments. Generated documentation is available here and under each module's namespace URI.

License

All code is made available under the BSD 2-Clause License except where explicitly marked otherwise.