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

data-structures haskell

Question

Hay una gran cantidad de textos en estructuras de datos y bibliotecas de código de estructuras de datos. Entiendo que la estructura de datos puramente funcional es más fácil de razonar. Sin embargo, tengo problemas para comprender la ventaja del mundo real de utilizar una estructura de datos puramente funcional en un código pragmático (utilizando lenguaje de programación funcional o no) sobre la contraparte imperativa. ¿Puede alguien proporcionar algunos casos del mundo real donde la estructura de datos puramente funcional tiene una ventaja y por qué?

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

Gracias.

PD: lo que quiero decir con una estructura de datos puramente funcional no es lo mismo que una estructura de datos persistente. ¿La 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

Además de la seguridad de memoria compartida, la mayoría de las estructuras de datos puramente funcionales también le proporcionan persistencia , y prácticamente de forma gratuita. Por ejemplo, digamos que tengo un set en OCaml, y quiero agregarle algunos valores nuevos. 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
...

a permanece sin modificar después de agregar los nuevos caracteres (solo contiene el anuncio), mientras que b contiene ah, y comparten parte de la misma memoria (con un set es complicado decir cuánta memoria se comparte, ya que es un árbol AVL y el forma de los cambios de árbol). Puedo continuar haciendo esto, haciendo un seguimiento de todos los cambios que he hecho en el árbol, lo que me permite volver a un estado anterior.

Aquí hay un gran diagrama del en.wikipedia.org/wiki/Purely_functional que muestra los resultados de insertar el carácter ''e'' en el árbol binario xs :

Answer 2

Las estructuras de datos puramente funcionales (también conocidas como persistentes o inmutables) le ofrecen varias ventajas:

• nunca tiene que bloquearlos, lo que mejora la simultaneidad .
• pueden compartir estructura, lo que reduce el uso de memoria . Por ejemplo, considere la lista [1, 2, 3, 4] en Haskell y algún lenguaje imperativo como Java. Para producir una nueva lista en Haskell, solo tiene que crear nuevas cons (par de valor y referencia-al-siguiente-elemento) y conectarla a la lista anterior. En Java tienes que crear una lista completamente nueva para no dañar la anterior.
• puede hacer que las estructuras de datos persistentes sean lazy .
• Además, si usa un estilo funcional, puede evitar pensar en el tiempo y la secuencia de operaciones , y por lo tanto, hacer que sus programas sean más declarative .
• De hecho, que la estructura de datos es inmutable, le permite hacer algunas suposiciones más y así expandir las capacidades del lenguaje . Por ejemplo, Clojure usa el hecho de la inmutabilidad para proporcionar correctamente las implementaciones del método hashCode () en cada objeto, por lo que cualquier objeto puede usarse como clave en un mapa.
• con datos inmutables y estilo funcional, también puede usar libremente la memoization .

Hay muchas más ventajas, en general, es otra forma de modelar el mundo real. This y algunos otros capítulos del SICP le brindarán una visión más precisa de la programación con estructuras inmutables, sus ventajas y desventajas.

Answer 3

Las estructuras de datos puramente funcionales tienen las siguientes ventajas:

• Persistencia: las versiones antiguas se pueden reutilizar de forma segura sabiendo que no se pueden haber cambiado.

• Compartir: muchas versiones de una estructura de datos pueden mantenerse simultáneamente con solo requisitos de memoria modestos.

• Seguridad de subprocesos: cualquier mutación está oculta dentro de los subprocesos perezosos (si corresponde) y, por lo tanto, se maneja según la implementación del lenguaje.

• Simplicidad: no tener que realizar un seguimiento de los cambios de estado simplifica el uso de las estructuras de datos puramente funcionales, particularmente en el contexto de la concurrencia.

• Incrementalidad: las estructuras de datos puramente funcionales se componen de muchas partes diminutas, lo que las hace ideales para la recolección incremental de basura que conduce a latencias más bajas.

Tenga en cuenta que no he enumerado el paralelismo como una ventaja de las estructuras de datos puramente funcionales porque no creo que este sea el caso. El paralelismo multinúcleo eficiente requiere una localidad predecible para aprovechar las cachés y evitar ser embotellado en el acceso compartido a la memoria principal y las estructuras de datos puramente funcionales tienen, en el mejor de los casos, características desconocidas en este sentido. En consecuencia, muchos programas que usan estructuras de datos puramente funcionales no se escalan bien cuando se paralelizan en un multinúcleo porque pasan todo su tiempo en errores de caché, compitiendo por vías de memoria compartidas.

Lo que quiero decir con una estructura de datos puramente funcional no es lo mismo que una estructura de datos persistente.

Hay algo de confusión aquí. En el contexto de estructuras de datos puramente funcionales, la persistencia es un término utilizado para referirse a la capacidad de volver a referirse a versiones anteriores de una estructura de datos segura sabiendo que todavía son válidas. 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.

Answer 4

Los programas de Erlang usan estructuras de datos puramente funcionales casi exclusivamente, y obtienen beneficios sustanciales escalando casi sin problemas a múltiples núcleos. Debido a que los datos compartidos (principalmente binarios y cadenas de bits) nunca se modifican, nunca es necesario bloquear dichos datos.

Answer 5

Toma este pequeño fragmento de F #:

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

Puede decir con 100% de certeza que esa es una lista inmutable de los números enteros del 1 al 5. Puede pasar una referencia a esa lista y nunca tener que preocuparse de que la lista haya sido modificada. Esa es razón suficiente para usarlo.