Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging dictionaries ("A Simple Mergeable Dictionary" by Adam Karczmarz),
By dynamic trees I refer to the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Few efforts have been published within the functional programming research area since.
- Edward Kmett implemented a version of the ST trees mostly as a translation of the C++ counterpart, see Link-cut trees.
- Chris Okasaki wrote a limited implementation of the Splay trees in his renowned book "Purely functional data structures".
- Ralf Hinze and Ross Paterson introduced a functional data structure called 2-3 finger trees but with somewhat different aim from that of original definition of dynamic trees.
Implementation (and perhaps performance) of dynamic trees are divided according to three approaches:
- Linearization, where ET trees (Euler tour) play a great role. Not found a purely functional study.
- Path-decomposition, where ST trees are the flagship, just found the Kmett's version.
- Tree contraction, where Top trees, topology trees and RC trees are the players. Not found a purely functional study.
Purely functional analysis and implementation can be found on Splay, AVL, red-black tree, but those are NOT dynamic trees. The former are considered the shadow (also called virtual or auxiliary) data structure of the latter.
So, my question is:
What are the reasons (drawbacks, weaknesses) for the Functional Programming research community not to take part into the dynamic trees data structure?
