Me gustaría aprender a hacer gráficos y realizar algunas operaciones locales en Haskell, pero la pregunta no es específica de Haskell, y en lugar de gráficos podemos considerar listas doblemente vinculadas.
Pregunta: ¿Cuál sería una forma idiomática o recomendada de implementar una lista doblemente enlazada (u otra estructura de datos doblemente enlazada o circular) y operaciones en un lenguaje que apoye y defienda principalmente estructuras de datos inmutables (Haskell, Clojure, etc.) ? En particular, ¿cómo usar las actualizaciones en el lugar, que están formalmente prohibidas por el idioma?
Puedo imaginar fácilmente que si se realiza alguna operación local en una lista doblemente vinculada (si se inserta un elemento, por ejemplo), puede que no sea necesario copiar toda la lista inmediatamente debido a la flojera del idioma. Sin embargo, dado que la lista está doblemente vinculada, si se modifica en un lugar, ninguno de los nodos antiguos se puede usar en la nueva versión de la lista, y necesitarían ser marcados, copiados, recolectados de basura de alguna manera tarde o temprano. . Obviamente, estas son operaciones redundantes si solo se utilizara la copia actualizada de la lista, pero agregarían una "sobrecarga" proporcional al tamaño de la lista.
¿Significa esto que para esas tareas los datos inmutables son simplemente inapropiados y que los lenguajes declarativos funcionales sin soporte "nativo" para datos mutables no son tan buenos como los imperativos? O, ¿hay alguna solución difícil?
PD: He encontrado algunos artículos y presentaciones sobre este tema en Internet, pero tuve dificultades para seguirlos, aunque creo que la respuesta a esta pregunta no debería tomar más de un párrafo y tal vez un diagrama ... Quiero decir, si hay no hay una solución "funcional" para este problema, la respuesta probablemente sea "usar C". Si hay uno, entonces, ¿qué tan complicado puede ser?
Preguntas relacionadas
"Estructuras de datos en programación funcional" . Mi pregunta específica sobre el uso de actualizaciones en el lugar en lugar de alternativas ineficientes no se discute allí.
"Mutación interna de estructuras de datos persistentes" . Allí el énfasis parece estar en la implementación de bajo nivel en un lenguaje no especificado, mientras que mi pregunta es sobre la elección correcta de un idioma (funcional o no) y sobre posibles soluciones idiomáticas en lenguajes funcionales.
Citas relevantes
Los lenguajes de programación puramente funcionales permiten que muchos algoritmos se expresen de manera muy concisa, pero hay algunos algoritmos en los que el estado actualizable en el lugar parece desempeñar un papel crucial. Para estos algoritmos, los lenguajes puramente funcionales, que carecen de estado actualizable, parecen ser inherentemente ineficientes ( [Ponder, McGeer y Ng, 1988] ).
- John Launchbury y Simon Peyton Jones, Hilos de estado funcional perezoso (1994), también John Launchbury y Simon Peyton Jones, Estado en Haskell (1995). Estos documentos introducen el STconstructor de tipo monádico en Haskell.
DiffArraytipo. Mirando la fuente del paquete diffarray , veo 91 ocurrencias deunsafePerformIO. Parece que la respuesta a mi pregunta es "sí, no, los lenguajes puramente funcionales con datos inmutables no son apropiados para implementar algoritmos que normalmente dependen de actualizaciones en el lugar".Map,IntMapoHashMap) como un almacenamiento y para hacer nodos contienen identificadores de los nodos vinculados. "Todos los problemas en informática pueden resolverse mediante otro nivel de indirección".Respuestas:
Podría haber otras estructuras de datos inmutables eficientes que se ajusten a su tarea particular, pero que no sean tan generales como una lista doblemente vinculada (que desafortunadamente es propensa a errores de modificación concurrentes debido a su mutabilidad). Si especifica su problema de manera más específica, tal estructura probablemente se pueda encontrar.
La respuesta general para el recorrido (relativamente) económico de estructuras inmutables es lentes. La idea es que puede mantener la información suficiente para reconstruir una estructura inmutable modificada a partir de sus partes no modificadas y la pieza actualmente modificada, y navegar sobre ella a un nodo vecino.
Otra estructura útil es una cremallera . (La parte divertida es que la firma de tipo para una cremallera de
lentees una derivada matemática escolar de una firma de tipo de la estructura).Aqui hay unos cuantos enlaces.
Un capítulo sobre cremalleras de "Learn you a Haskell"
Introducción a las lentes en Scala (diapositivas)
fuente
Haskell no impide el uso de estructuras de datos mutables. Se desaconsejan y se hacen más difíciles de usar debido al hecho de que las partes del código que los usan deben devolver una acción IO (que finalmente debe estar vinculada a la acción IO que devuelve la función principal), pero eso no hacer que sea imposible usar tales estructuras si realmente las necesita.
Sugeriría investigar el uso de la memoria transaccional de software como un camino a seguir. Además de proporcionar una forma eficiente de implementar estructuras mutables, también ofrece garantías muy útiles para la seguridad de los hilos. Consulte la descripción del módulo en https://hackage.haskell.org/package/stm y la descripción general de la wiki en https://wiki.haskell.org/Software_transactional_memory .
fuente
MVar,State,ST), por lo que voy a tener que averiguar sus diferencias y usos previstos.STIMO, debería mencionarse en la respuesta porque permite ejecutar un cálculo con estado, luego descartar el estado y extraer el resultado como un valor puro.STcon STM para tener concurrencia y estado desechable?mainvariable. :) (mainni siquiera tiene una función.)