¿Cuál es el beneficio de la estructura de datos puramente funcional?

Question

Hay un gran número de textos sobre las estructuras de datos y bibliotecas de código de estructuras de datos. Yo entiendo que la estructura de datos puramente funcional es más fácil de razonar acerca. Sin embargo tengo problemas para comprender la verdadera ventaja del mundo usando la estructura de datos puramente funcional en clave pragmática (utilizando un lenguaje de programación funcional o no) sobre la contraparte imprescindible. Alguien puede proporcionar algunos casos del mundo real, donde la estructura de datos puramente funcional tiene la ventaja y por qué?

Ejemplos lo largo de la línea como yo uso data_structure_name en programming_language hacer aplicación porque puede hacer certain_thing .

Gracias.

PS: ¿Qué quiero decir con estructura de datos puramente funcional no es la misma que la estructura de datos persistente. estructura de datos persistente es una estructura de datos que no cambia ?? Por otro lado la estructura de datos puramente funcional es una estructura de datos que opera puramente.

Answer 1

estructuras de datos puramente funcional (también conocido como persistente o inmutable) le dan varias ventajas:

• que nunca tiene que encerrarlos, lo que mejora extremadamente concurrencia .
• pueden compartir estructura, que reduce el uso de memoria . Por ejemplo, la lista [1, 2, 3, 4] en Haskell y algo de lenguaje imperativo considerar como Java. Para producir nueva lista en Haskell es suficiente con crear una nueva cons (par de valor y referencia-a-lado-elemento) y conectarlo a la lista anterior. En Java hay que crear completamente nueva lista de no dañar la anterior.
• se puede hacer estructuras de datos persistentes perezoso .
• también, si utiliza el estilo funcional, puede evitar pensar en el tiempo y secuencia de operaciones , y así, hacer que sus programas sean más declarativa .
• hecho, que la estructura de datos es inmutable, le permite hacer algunas suposiciones más y de modo ampliar las capacidades del lenguaje . Por ejemplo, Clojure utiliza el hecho de inmutabilidad a correctamente proporcionar implementaciones del procedimiento en cada objeto hashCode (), por lo que cualquier objeto puede ser utilizado como una llave en un mapa.
• con los datos inmutables y estilo funcional también se puede utilizar libremente memoization .

Hay mucho más ventajas, en general, es otra manera de modelar el mundo real. Este y alguna otra capítulos de SICP le dará visión más precisa de la programación con estructuras inmutables, sus ventajas y desventajas.

Answer 2

Además de la seguridad de memoria compartida más puramente estructuras de datos de función también le dan persistencia , y prácticamente de forma gratuita. Por ejemplo, digamos que tengo una set en OCaml, y quiero añadir algunos nuevos valores a los que puedo hacer esto:

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

restos a modificar después de la adición de los nuevos personajes (que sólo contiene publicidad), mientras que b contiene ah, y comparten algunas de la misma memoria (con un set que es un poco difícil de decir cuánto la memoria es compartida, ya que es un árbol AVL y la forma de los cambios en el árbol). Puedo seguir haciendo esto, hacer el seguimiento de todos los cambios que he hecho en el árbol que me permite volver a un estado anterior.

Aquí está un gran diagrama de la puramente funcional que muestra los resultados de la inserción carácter 'e' en el xs árbol binario:

Answer 3

Programas de Erlang utilizar estructuras de datos puramente funcionales casi exclusivamente, y que obtienen beneficios sustanciales mediante el escalado casi a la perfección con múltiples núcleos. Debido a que los datos compartidos (principalmente binarios y cadenas de bits) no se modifica nunca, nunca hay una necesidad de bloquear tales datos.

Answer 4

Tome este pequeño fragmento de F #:

let numbers = [1; 2; 3; 4; 5]

Se puede decir con 100% de certeza de que esto es una lista inmutable de números enteros de 1 a 5. Puede pasar alrededor de una referencia a esa lista y no tiene que preocuparse de que la lista puede haber sido modificado. Esa es una razón suficiente para que la utilice.

Answer 5

estructuras de datos puramente funcionales tienen las siguientes ventajas:

• Persistencia:. Versiones antiguas pueden ser reutilizados con la certeza de que no se han cambiado

• Compartir:. Muchas versiones de una estructura de datos se pueden mantener simultáneamente con los requisitos de memoria modestos

• Seguridad de los hilos:. Ninguna mutación se oculta dentro de los procesadores de descanso (si existe) y, por lo tanto, a cargo de la implementación del lenguaje

• Simplicidad:. No tener que seguir la pista de los cambios de estado hace que las estructuras de datos puramente funcionales más fácil de usar, particularmente en el contexto de concurrencia

• incrementalidad:. Estructuras de datos puramente funcionales se componen de muchas piezas pequeñas, haciéndolos ideales para la recolección de basura que provoca una disminución latencias

Tenga en cuenta que no he enumerado paralelismo como una ventaja de estructuras de datos puramente funcionales, porque no creo que este sea el caso. paralelismo multinúcleo eficiente requiere localidad predecible con el fin de aprovechar las cachés y evitar ser un cuello de botella en el acceso compartido a la memoria principal y estructuras de datos puramente funcionales tienen, en el mejor de características desconocidas en este sentido. En consecuencia, muchos programas que utilizan estructuras de datos puramente funcionales no se escalan bien cuando parallelized en un multi-núcleo, ya que pasan todo su tiempo en fallos de caché, contendiendo por vías de memoria compartida.

Lo que quiero decir con estructura de datos puramente funcional no es la misma que la estructura de datos persistente.

Hay una cierta confusión en este punto. En el contexto de estructuras de datos puramente funcionales, la persistencia es un término usado para referirse a la capacidad para hacer referencia de nuevo a las versiones anteriores de una caja fuerte de estructura de datos en el conocimiento de que siguen siendo válidos. Este es un resultado natural de ser puramente funcional y, por lo tanto, la persistencia es una característica inherente de todas las estructuras de datos puramente funcionales.