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?


migrated from stackoverflow.com Jul 3 '16 at 19:29

This question came from our site for professional and enthusiast programmers.

  • 11
    $\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$ – Andrej Bauer Jul 4 '16 at 11:40

"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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.