¿Cómo manejan los lenguajes de programación puramente funcionales los datos que cambian rápidamente?

¿Qué estructuras de datos puede usar para obtener la eliminación y el reemplazo de O (1)? ¿O cómo puede evitar situaciones en las que necesita dichas estructuras?

Existe una amplia gama de estructuras de datos que aprovechan la pereza y otros trucos para lograr un tiempo constante amortizado o incluso (para algunos casos limitados, como colas ) actualizaciones de tiempo constante para muchos tipos de problemas. La tesis doctoral de Chris Okasaki "Estructuras de datos puramente funcionales" y el libro del mismo nombre es un excelente ejemplo (quizás el primero importante), pero el campo ha avanzado desde entonces . Estas estructuras de datos generalmente no solo son puramente funcionales en la interfaz, sino que también se pueden implementar en Haskell puro y lenguajes similares, y son completamente persistentes.

Incluso sin ninguna de estas herramientas avanzadas, los simples árboles de búsqueda binarios balanceados brindan actualizaciones de tiempo logarítmico, por lo que la memoria mutable se puede simular con, en el peor de los casos, una desaceleración logarítmica.

Hay otras opciones, que pueden considerarse trampas, pero son muy efectivas con respecto al esfuerzo de implementación y el rendimiento en el mundo real. Por ejemplo, los tipos lineales o los tipos de unicidad permiten la actualización en el lugar como estrategia de implementación para un lenguaje conceptualmente puro, al evitar que el programa se aferre al valor anterior (la memoria que estaría mutada). Esto es menos general que las estructuras de datos persistentes: por ejemplo, no puede crear fácilmente un registro de deshacer almacenando todas las versiones anteriores del estado. Sigue siendo una herramienta poderosa, aunque AFAIK aún no está disponible en los principales lenguajes funcionales.

Otra opción para introducir de forma segura el estado mutable en un entorno funcional es la STmónada en Haskell. Se puede implementar sin mutación y, salvo las unsafe*funciones, se comporta como si fuera solo un sofisticado envoltorio para pasar implícitamente una estructura de datos persistente (cf. State). Pero debido a algún tipo de truco del sistema que impone el orden de evaluación y evita el escape, puede implementarse de manera segura con la mutación en el lugar, con todos los beneficios de rendimiento.

Una estructura mutable barata es la pila de argumentos.

Eche un vistazo al típico cálculo factorial de estilo SICP:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

Como puede ver, el segundo argumento de facse utiliza como un acumulador mutable para contener el producto que cambia rápidamente n * (n-1) * (n-2) * .... Sin embargo, no hay ninguna variable mutable a la vista, y no hay forma de alterar inadvertidamente el acumulador, por ejemplo, desde otro hilo.

Este es, por supuesto, un ejemplo limitado.

Puede obtener listas enlazadas inmutables con un reemplazo económico del nodo principal (y, por extensión, cualquier parte que comience desde la cabeza): simplemente haga que la nueva cabeza apunte al mismo nodo siguiente que la cabeza anterior. Esto funciona bien con muchos algoritmos de procesamiento de listas ( foldbasados ​​en cualquier cosa ).

Puede obtener un rendimiento bastante bueno de las matrices asociativas basadas, por ejemplo, en HAMT . Lógicamente, recibe una nueva matriz asociativa con algunos pares de valores clave cambiados. La implementación puede compartir la mayoría de los datos comunes entre los objetos antiguos y los recién creados. Sin embargo, esto no es O (1); generalmente obtienes algo logarítmico, al menos en el peor de los casos. Los árboles inmutables, por otro lado, generalmente no sufren ninguna penalización de rendimiento en comparación con los árboles mutables. Por supuesto, esto requiere un poco de sobrecarga de memoria, generalmente lejos de ser prohibitivo.

Otro enfoque se basa en la idea de que si un árbol cae en un bosque y nadie lo escucha, no necesita producir sonido. Es decir, si puede probar que un poco de estado mutado nunca deja algún alcance local, puede mutar los datos dentro de él de manera segura.

Clojure tiene transitorios que son 'sombras' mutables de estructuras de datos inmutables que no se escapan fuera del alcance local. Clean usa Uniques para lograr algo similar (si no recuerdo mal). Rust ayuda a hacer cosas similares con punteros únicos estáticamente controlados.

Lo que preguntas es demasiado amplio. O (1) remoción y reemplazo desde qué posición? La cabeza de una secuencia? ¿La cola? ¿Una posición arbitraria? La estructura de datos a utilizar depende de esos detalles. Dicho esto, 2-3 Finger Trees parecen una de las estructuras de datos persistentes más versátiles que existen:

Presentamos 2-3 árboles de dedos, una representación funcional de secuencias persistentes que apoyan el acceso a los extremos en tiempo constante amortizado, y concatenación y división en tiempo logarítmico en el tamaño de la pieza más pequeña.

(...)

Además, al definir la operación de división en una forma general, obtenemos una estructura de datos de propósito general que puede servir como secuencia, cola de prioridad, árbol de búsqueda, cola de búsqueda de prioridad y más.

En general, las estructuras de datos persistentes tienen un rendimiento logarítmico al modificar posiciones arbitrarias. Esto puede o no ser un problema, ya que la constante en un algoritmo O (1) puede ser alta, y la desaceleración logarítmica podría ser "absorbida" en un algoritmo general más lento.

Más importante aún, las estructuras de datos persistentes facilitan el razonamiento sobre su programa, y ​​ese siempre debe ser su modo de operación predeterminado. Debe favorecer las estructuras de datos persistentes siempre que sea posible, y solo usar una estructura de datos mutable una vez que haya perfilado y determinado que la estructura de datos persistentes es un cuello de botella en el rendimiento. Cualquier otra cosa es la optimización prematura.