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.

  1. Edward Kmett implemented a version of the ST trees mostly as a translation of the C++ counterpart, see Link-cut trees.
  2. Chris Okasaki wrote a limited implementation of the Splay trees in his renowned book "Purely functional data structures".
  3. 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:

  1. Linearization, where ET trees (Euler tour) play a great role. Not found a purely functional study.
  2. Path-decomposition, where ST trees are the flagship, just found the Kmett's version.
  3. 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?

  • 16
    $\begingroup$ I don't understand how this can possibly be answered without forming an Authoritative Functional Programming Community Committee for Forming Official Opinions. Can't we reformulate the question so that there's something that can be answered here? As far as I can tell, the OP should just go and implement his dynamic trees in Haskell or whatever and then come back here to report that it has been done after all. $\endgroup$ Commented Jul 4, 2016 at 11:40
  • 2
    $\begingroup$ Update to @AndrejBauer: the OP has gone and implemented his dynamic trees in Haskell: arxiv.org/abs/1908.11105 $\endgroup$
    – jbapple
    Commented Sep 15, 2019 at 23:59
  • $\begingroup$ Can we please be careful not to equating "Purely Functional Data Structures" with the terms "Functional Programming" or "Functional Programming research community"? As someone into data structures glad this has a name, but as an actual working functional programmer, it's incredibly annoying. I'd like "functional programming" to denote things like infinite trees and sequences, or storing data as functions. $\endgroup$ Commented Oct 9, 2020 at 12:26

1 Answer 1


"In computer science, functional programming is a programming paradigm. A style of building the structure and elements of computer programs that treats computation as the evaluation of mathematical functions and avoids changing state and mutable data." - Wikipedia

"changing state and mutable data" in other words "dynamic".

So your question is a bit like asking why left isn't right.

  • 1
    $\begingroup$ Functional programs can represent dynamic data with persistent data structures. This question is asking why development of persistent data structures for a certain problem has not been researched. The question makes sense. $\endgroup$ Commented Sep 15, 2019 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.