Continuing with the post "Ongoing xslt/xquery spec update" we would like to articulate what options regarding associative containers do we have in a functional languages (e.g. xslt, xquery), assuming that variables are immutable and implementation is efficient (in some sense).

There are three common implementation techniques:

• store data (keys, value pairs) in sorted array, and use binary search to access values by a key;
• store data in a hash map;
• store data in a binary tree (usually RB or AVL trees).

Implementation choice considerably depends on operations, which are taken over the container. Usually these are:

1. construction;
2. value lookup by key;
3. key enumeration (ordered or not);
4. container modification (add and remove data into the container);
5. access elements by index;

Note that modification in a functional programming means a creation of a new container, so here is a division:

1. If container's use pattern does not include modification, then probably the simplest solution is to build it as an ordered sequence of pairs, and use binary search to access the data. Alternatively, one could implement associative container as a hash map.
2. If modification is essential then neither ordered sequence of pairs, hash map nor classical tree implementation can be used, as they are either too slow or too greedy for a memory, either during modification or during access.

On the other hand to deal with container's modifications one can build an implementation, which uses "top-down" RB or AVL trees. To see the difference consider a classical tree structure and its functional variant:

Here we observe that:

1. one can implement efficient map (lookup time no worse than O(LnN)) with no modification support, using ordered array;
2. one can implement efficient map with support of modification, using immutable binary tree;
3. one can implement all these algorithms purely in xslt and xquery (provided that inline functions are supported);
4. any such imlementation will lose against the same implementation written in C++, C#, java;
5. the best implementation would probably start from sorted array and will switch to binary tree after some size threshold.

Here we provide a C# implementation of a functional AVL tree, which also supports element indexing:

• AVLTreeNavigator.cs
• Program.cs

Our intention was to show that the usual algorithms for associative containers apply in functional programming; thus a feature complete functional language must support associative containers to make development more conscious, and to free a developer from inventing basic things existing already for almost a half of century.