Como descubrí, las variables en Haskell son inmutables (por lo tanto, no son realmente "variables").Estructuras de datos complejas en Haskell: ¿cómo funcionan?
En este caso, si tenemos una estructura de datos compleja y grande, como un árbol rojo-negro, ¿cómo se supone que implementaremos operaciones que realmente cambien la estructura de datos?
¿Crea una copia del árbol cada vez que se inserta o elimina un elemento?
Sí, la solución es devolver una nueva estructura de datos que represente el valor modificado; sin embargo, no es necesario copiar toda la estructura para su ejemplo (árboles rojo-negro) ya que solo puede copiar los nodos en la ruta desde la raíz hasta el nodo insertado. Esto permite que la operación de inserción tenga la misma complejidad que la versión imperativa. de
Chris Okasaki Purely functional data structures contiene una serie de implementaciones de estructuras de datos inmutables - este libro es una versión modificada de su tesis doctoral, que se puede encontrar here
Y para ir más allá del libro de Okasaki: [¿Qué hay de nuevo en las estructuras de datos puramente funcionales desde Okasaki?] (Http://cstheory.stackexchange.com/questions/ 1539/whats-new-in-purely-functional-data-structures-since-okasaki) – Gilles
La tesis doctoral es un enlace inactivo. – fuz
@FUZxxl: parece que citeseerx.ist.psu.edu ha caído por alguna razón, esperemos que vuelva. –
Su intuición acerca de la copia es exactamente la dirección correcta que debe estar pensando. Sin embargo, la 'copia' inteligentemente implementada por el tiempo de ejecución de Haskell. Por ejemplo, dada
data Tree = Empty | Branch Tree Integer Tree
Se podría implementar una función para reemplazar la rama izquierda:
replaceLeft :: Tree -> Tree -> Tree
replaceLeft (Branch _ i r) newLeft = Branch newLeft i r
El resultado no es que se crea una copia completa del nuevo árbol, ya que no es necesario. El valor i y los árboles r y newLeft no se modifican, por lo que no es necesario copiar sus contenidos en la memoria nueva.
El nuevo Branch creado (esta es la única asignación real en este ejemplo: la creación de la estructura para contener los árboles izquierdo/derecho en el Integer) sigue haciendo referencia a los mismos valores de la rama anterior, sin copia ¡necesario!
Dado que las estructuras de datos son inmutables, no hay ningún problema al hacerlo.
Me gusta la atención a la inmutabilidad: es precisamente la inmutabilidad que nos permite lograr esta compartiendo. – luqui
"Por lo tanto, no son realmente \ 'variables'" - Claro que sí. Por ejemplo, cuando un matemático dice "Let * G * sea el grupo (* S *, \ *), where ...", la * G * es una variable, aunque nunca va a cambiar. Es el mismo principio en Haskell. –
ciertamente plantea un punto interesante, de hecho la estructura cambia un poco para acomodar la inmutabilidad sin sacrificar el rendimiento. Piense en su estructura como un gráfico orientado (donde un borde de A a B significa que A tiene una referencia/índice de B), luego si desea cambiar B, cualquier vértice desde el cual B fue accesible debe ser copiado y su referencia actualizada . Todavía no he encontrado cómo representar una lista de saltos en Haskell, por ejemplo :) –