¿Por qué la programación funcional no ha investigado los árboles dinámicos?

19

Los árboles dinámicos desempeñan un papel importante en la resolución de problemas tales como flujos de red, gráficos dinámicos, problemas combinatorios ("Árboles dinámicos en la práctica" de Tarjan y Werneck) y diccionarios recientemente fusionados ("Un diccionario fusionable simple" de Adam Karczmarz),

Por árboles dinámicos me refiero a la definición establecida en el documento de Sleator & Tarjan "Una estructura de datos para árboles dinámicos" en 1983. Desde entonces se han publicado pocos esfuerzos dentro del área de investigación de programación funcional.

  1. Edward Kmett implementó una versión de los árboles ST principalmente como una traducción de la contraparte C ++, ver Árboles cortados por enlaces .
  2. Chris Okasaki escribió una implementación limitada de los árboles Splay en su famoso libro "Estructuras de datos puramente funcionales".
  3. Ralf Hinze y Ross Paterson introdujeron una estructura de datos funcional llamada 2-3 árboles de dedos, pero con un objetivo algo diferente del de la definición original de árboles dinámicos.

La implementación (y quizás el rendimiento) de los árboles dinámicos se divide de acuerdo con tres enfoques:

  1. Linealización, donde los árboles ET (Euler tour) juegan un gran papel. No se encontró un estudio puramente funcional.
  2. La descomposición del camino, donde los árboles ST son el buque insignia, acaba de encontrar la versión de Kmett.
  3. Contracción de árboles, donde los árboles superiores, los árboles de topología y los árboles RC son los jugadores. No se encontró un estudio puramente funcional.

El análisis y la implementación puramente funcional se pueden encontrar en Splay, AVL, árbol rojo-negro, pero NO son árboles dinámicos. Los primeros se consideran la estructura de datos sombra (también llamada virtual o auxiliar) de los segundos.

Entonces, mi pregunta es:

¿Cuáles son las razones (inconvenientes, debilidades) para que la comunidad de investigación de Programación Funcional no participe en la estructura de datos de los árboles dinámicos?

data-structures trees functional-programming Richard Chambers
fuente
14
No entiendo cómo esto puede ser respondido sin formar un Comité de la Comunidad de Programación Funcional Autorizada para Formar Opiniones Oficiales. ¿No podemos reformular la pregunta para que haya algo que pueda responderse aquí? Por lo que puedo decir, el OP debería ir e implementar sus árboles dinámicos en Haskell o lo que sea y luego regresar aquí para informar que se ha hecho después de todo.
Andrej Bauer el
Actualización a @AndrejBauer: el OP se fue e implementó sus árboles dinámicos en Haskell: arxiv.org/abs/1908.11105
jbapple

Respuestas:

-1

"En informática, la programación funcional es un paradigma de programación. Un estilo de construcción de la estructura y los elementos de los programas informáticos que trata la computación como la evaluación de funciones matemáticas y evita el cambio de estado y datos mutables". - Wikipedia

"estado cambiante y datos mutables" en otras palabras "dinámico".

Entonces su pregunta es un poco como preguntar por qué la izquierda no es la correcta.

Anthony Bachler
fuente
1
Los programas funcionales pueden representar datos dinámicos con estructuras de datos persistentes. Esta pregunta es por qué no se ha investigado el desarrollo de estructuras de datos persistentes para un determinado problema. La pregunta tiene sentido.
Vuelve a instalar a Monica el