¿Por qué los árboles de extensión persistentes son particularmente útiles en la programación funcional?

Question

Sobre el Árboles Página de Wikipedia Se dice (en la sección de ventajas):

Posibilidad de crear una versión de estructura de datos persistente de árboles de extensiones, lo que permite el acceso a las versiones anteriores y nuevas después de una actualización. Esto puede ser útil en la programación funcional, y requiere espacio amortizado O (log n) por actualización.

¿Porqué es eso? ¿Cómo es la programación funcional? árboles de extensión persistentes?

Answer 1

Uno de los objetivos de conducción de la programación funcional moderna es una mejor gestión del estado, de preferiblemente utilizando tan poco de ella como sea necesario, ya que los programas con estado deben ejecutar cuidadosamente los comandos en la secuencia correcta para evitar errores.

Las estructuras de datos persistentes son grandes precisamente porque no usan un estado mutable, lo que les permite usar en cálculos puros e inmutables

//mutable tree
var t = new_tree();
add(t, 1);
add(t, 2);
//the tree has now changed so if anyone was depending on the old value
//we will now have a problem

//persistent tree
var t = new_tree();
var t2 = add(t, 1);
var t3 = add(t2, 2);
//t1 and t2 have not changed

La cita que señaló es solo enfatizar que las estructuras de datos persistentes se usan comúnmente (y se prefieren) en la programación funcional pura. No hay nada particular en los árboles de extensión en este caso.

Answer 2

Su pregunta parece provenir de un poco desafortunado de confusión terminológica. Una mejor frase podría ser puramente funcional, es decir, programación funcional sin mutación destructiva. La confusión probablemente surge del hecho de que las estructuras de datos inmutables y persistentes son más comunes en la programación funcional en su conjunto, por una variedad de razones.

En resumen, probablemente pueda leer esa frase como "crear árboles de extensión persistentes puede ser útiles al programar solo con estructuras de datos inmutables", que limita con lo tautológico.

Answer 3

Incluso argumentaría lo contrario, los árboles de extensión son menos cómodos para trabajar en programación funcional porque necesita devolver el nuevo árbol incluso después de cada operación de búsqueda y realizar un seguimiento del último árbol para casi todas las operaciones. Además, todos los árboles de búsqueda que conozco se pueden usar directamente funcionalmente con O (log n) espacio adicional por operación. Supongo que el único hecho interesante en esa oración de que el requisito de memoria por operación permanece (log n) amortizado, a pesar de que reestructuramos el árbol todo el tiempo, pero observe que ahora pagamos ese precio de espacio incluso por las búsquedas.