Estructuras inmutables y jerarquía de composición profunda.

Estoy desarrollando una aplicación de interfaz gráfica de usuario, que trabaja mucho con gráficos; puede pensar en ello como un editor de vectores, por el bien del ejemplo. Es muy tentador hacer que todas las estructuras de datos sean inmutables, por lo que podría deshacer / rehacer, copiar / pegar y muchas otras cosas casi sin esfuerzo.

En aras de la simplicidad, utilizaré el siguiente ejemplo: la aplicación se utiliza para editar formas poligonales, por lo que tengo el objeto "Polígono", que es simplemente una lista de puntos inmutables:

Scene -> Polygon -> Point

Entonces, solo tengo una variable mutable en mi programa, la que contiene el objeto Scene actual. El problema que tengo comienza cuando intento implementar el arrastre de puntos: en la versión mutable, simplemente agarro un Pointobjeto y comienzo a modificar sus coordenadas. En versión inmutable, estoy atascado. Podría haber almacenado índices de Polygoncorriente Scene, índice del punto arrastrado Polygony reemplazarlo cada vez. Pero este enfoque no escala: cuando los niveles de composición van a 5 y más, la repetitiva se volvería insoportable.

Estoy seguro de que este problema se puede resolver: después de todo, existe Haskell con estructuras completamente inmutables y mónada de E / S. Pero simplemente no puedo encontrar cómo.

¿Podrías darme una pista?

Podría haber almacenado índices de Polígono en la escena actual, índice del punto arrastrado en Polígono y reemplazarlo cada vez. Pero este enfoque no escala: cuando los niveles de composición van a 5 y más, la repetitiva se volvería insoportable.

Tienes toda la razón, este enfoque no se escala si no puedes evitar la barrera . Específicamente, se modificó la plantilla para crear una escena completamente nueva con una pequeña subparte. Sin embargo, muchos lenguajes funcionales proporcionan una construcción para lidiar con este tipo de manipulación de estructuras anidadas: lentes.

Una lente es básicamente un captador y configurador de datos inmutables. Una lente se centra en una pequeña parte de una estructura más grande. Dada una lente, hay dos cosas que puede hacer con ella: puede ver la pequeña parte de un valor de la estructura más grande, o puede establecer la pequeña parte de un valor de una estructura más grande en un nuevo valor. Por ejemplo, suponga que tiene una lente que se enfoca en el tercer elemento de una lista:

thirdItemLens :: Lens [a] a

Ese tipo significa que la estructura más grande es una lista de cosas, y la subparte pequeña es una de esas cosas. Dada esta lente, puede ver y configurar el tercer elemento de la lista:

> view thirdItemLens [1, 2, 3, 4, 5]
3
> set thirdItemLens 100 [1, 2, 3, 4, 5]
[1, 2, 100, 4, 5]

La razón por la que las lentes son útiles es porque son valores que representan captadores y definidores, y puede abstraerlos de la misma manera que lo hace con otros valores. Puede realizar funciones que devuelvan lentes, por ejemplo, una listItemLensfunción que toma un número ny devuelve una lente que visualiza el nelemento en una lista. Además, las lentes se pueden componer :

> firstLens = listItemLens 0
> thirdLens = listItemLens 2
> firstOfThirdLens = lensCompose firstLens thirdLens
> view firstOfThirdLens [[1, 2], [3, 4], [5, 6], [7, 8]]
5
> set firstOfThirdLens 100 [[1, 2], [3, 4], [5, 6], [7, 8]]
[[1, 2], [3, 4], [100, 6], [7, 8]]

Cada lente encapsula el comportamiento para atravesar un nivel de la estructura de datos. Al combinarlos, puede eliminar el repetitivo para atravesar múltiples niveles de estructuras complejas. Por ejemplo, suponiendo que tiene un scenePolygonLens ique ve el iPolígono en una Escena, y polygonPointLens nque ve el nthPunto en un Polígono, puede hacer un constructor de lentes para enfocarse solo en el punto específico que le interesa en una escena completa de esta manera:

scenePointLens i n = lensCompose (polygonPointLens n) (scenePolygonLens i)

Ahora suponga que un usuario hace clic en el punto 3 del polígono 14 y lo mueve 10 píxeles hacia la derecha. Puedes actualizar tu escena así:

lens = scenePointLens 14 3
point = view lens currentScene
newPoint = movePoint 10 0 point
newScene = set lens newPoint currentScene

Esto contiene muy bien toda la plantilla para atravesar y actualizar una escena en el interior lens, todo lo que tiene que preocuparse es a qué desea cambiar el punto. Puede resumir esto con una lensTransformfunción que acepta una lente, un objetivo y una función para actualizar la vista del objetivo a través de la lente:

lensTransform lens transformFunc target =
  current = view lens target
  new = transformFunc current
  set lens new target

Esto toma una función y la convierte en un "actualizador" en una estructura de datos complicada, aplicando la función solo a la vista y usándola para construir una nueva vista. Volviendo al escenario de mover el 3er punto del polígono 14 a los 10 píxeles correctos, eso se puede expresar en términos de la siguiente lensTransformmanera:

lens = scenePointLens 14 3
moveRightTen point = movePoint 10 0 point
newScene = lensTransform lens moveRightTen currentScene

Y eso es todo lo que necesitas para actualizar toda la escena. Esta es una idea muy poderosa y funciona muy bien cuando tiene algunas funciones agradables para construir lentes que visualizan los datos que le interesan.

Sin embargo, todo esto es bastante interesante actualmente, incluso en la comunidad de programación funcional. Es difícil encontrar un buen soporte de biblioteca para trabajar con lentes, y aún más difícil explicar cómo funcionan y cuáles son los beneficios para sus compañeros de trabajo. Toma este enfoque con un grano de sal.

He trabajado exactamente en el mismo problema (pero solo con 3 niveles de composición). La idea básica es clonar, luego modificar . En un estilo de programación inmutable, la clonación y la modificación tienen que suceder juntas, lo que se convierte en objeto de comando .

Tenga en cuenta que, en un estilo de programación mutable, la clonación habría sido necesaria de todos modos:

• Para permitir deshacer / rehacer
• Es posible que el sistema de visualización necesite mostrar simultáneamente el modelo "antes de editar" y "durante la edición", superpuestos (como líneas fantasmas), para que el usuario pueda ver los cambios.

En estilo de programación mutable,

• La estructura existente está clonada en profundidad.
• Los cambios se realizan en la copia clonada.
• Se le indica al motor de visualización que represente la estructura antigua en líneas fantasma y la estructura clonada / modificada en color.

En un estilo de programación inmutable,

• Cada acción del usuario que resulta en la modificación de datos se asigna a una secuencia de "comandos".
• Un objeto de comando encapsula exactamente qué modificación se aplicará y una referencia a la estructura original.
  • En mi caso, mi objeto de comando solo recuerda el índice de puntos que necesita ser cambiado y las nuevas coordenadas. (es decir, muy ligero, ya que no sigo estrictamente el estilo inmutable).
• Cuando se ejecuta un objeto de comando, crea una copia profunda modificada de la estructura, haciendo que la modificación sea permanente en la nueva copia.
• A medida que el usuario realice más ediciones, se crearán más objetos de comando.

Los objetos profundamente inmutables tienen la ventaja de que la clonación profunda de algo simplemente requiere copiar una referencia. Tienen la desventaja de que incluso un pequeño cambio en un objeto profundamente anidado requiere construir una nueva instancia de cada objeto dentro del cual está anidado. Los objetos mutables tienen la ventaja de que cambiar un objeto es fácil, solo hágalo, pero la clonación profunda de un objeto requiere la construcción de un nuevo objeto que contenga un clon profundo de cada objeto anidado. Peor aún, si uno quiere clonar un objeto y hacer un cambio, clonar ese objeto, hacer otro cambio, etc., sin importar cuán grandes o pequeños sean los cambios, uno debe mantener una copia de toda la jerarquía para cada versión guardada del estado del objeto Asqueroso.

Un enfoque que podría valer la pena considerar sería definir un tipo abstracto "quizás mutable" con tipos derivados derivables mutables y profundamente inmutables. Todos estos tipos tendrían un AsImmutablemétodo; llamar a ese método en una instancia profundamente inmutable de un objeto simplemente devolvería esa instancia. Llamarlo a una instancia mutable devolvería una instancia profundamente inmutable cuyas propiedades eran instantáneas profundamente inmutables de sus equivalentes en el original. Los tipos inmutables con equivalentes mutables tendrían un AsMutablemétodo que construiría una instancia mutable cuyas propiedades coincidieran con las del original.

Cambiar un objeto anidado en un objeto profundamente inmutable requeriría primero reemplazar el objeto inmutable externo por uno mutable, luego reemplazar la propiedad que contiene la cosa que se va a cambiar por una mutable, etc., pero realizar cambios repetidos en el mismo aspecto del el objeto general no requeriría hacer ningún objeto adicional hasta el momento en que se intentó llamar AsImmutablea un objeto mutable (lo que dejaría los objetos mutables mutables, pero devolvería objetos inmutables que contienen los mismos datos).

Como optimizaciones simples pero significativas, cada objeto mutable podría contener una referencia en caché a un objeto de su tipo inmutable asociado, y cada tipo inmutable debería almacenar en caché su GetHashCodevalor. Al invocar AsImmutableun objeto mutable, antes de devolver un nuevo objeto inmutable, verifique que coincida con la referencia en caché. Si es así, devuelva la referencia en caché (abandonando el nuevo objeto inmutable). De lo contrario, actualice la referencia almacenada en caché para contener el nuevo objeto y devuélvala. Si esto se hace, repetidas llamadas aAsImmutablesin ninguna mutación intermedia producirá las mismas referencias de objeto. Incluso si no se ahorra el costo de construir las nuevas instancias, se evitará el costo de memoria de mantenerlas. Además, las comparaciones de igualdad entre los objetos inmutables pueden acelerarse enormemente si en la mayoría de los casos los elementos que se comparan son de referencia igual o tienen códigos hash diferentes.