Administración de actualizaciones para estructuras de datos inmutables anidadas en lenguajes funcionales

Question

Me he dado cuenta en mi búsqueda de la programación funcional de que hay casos en que las listas de parámetros comienzan a ser excesivas cuando se usan estructuras de datos inmutables anidadas. Esto se debe a que al realizar una actualización de un estado de objeto, también debe actualizar todos los nodos principales en la estructura de datos. Tenga en cuenta que aquí tomo "actualización" para significar "devolver un nuevo objeto inmutable con el cambio apropiado".

p. Ej. el tipo de función que he encontrado a mí mismo escribiendo (Clojure ejemplo) es:

(defn update-object-in-world [world country city building object property value] 
    (update-country-in-world world 
    (update-city-in-country country 
     (update-building-in-city building 
     (update-object-in-building object property value))))) 

Todo esto para actualizar una propiedad simple es bastante feo, pero además de la persona que llama tiene que reunir todos los parámetros!

Esto debe ser un requisito bastante común cuando se trata de estructuras de datos inmutables en lenguajes funcionales en general, entonces ¿hay un buen patrón o truco para evitar esto que debería estar usando en su lugar?

Answer 1

Hay dos enfoques, que yo sepa:

recoger múltiples parámetros en una especie de objeto que es conveniente pasar alrededor. Ejemplo:

; world is a nested hash, the rest are keys 
(defstruct location :world :country :city :building) 
(defstruct attribute :object :property) 

(defn do-update[location attribute value] 
    (let [{:keys [world country city building]} location 
     {:keys [object property]} attribute ] 
    (update-in world [country city building object property] value))) 

Esto le lleva a dos parámetros que la persona que llama tiene que preocuparse (ubicación y atributo), que puede ser justo lo suficiente si esos parámetros no cambian muy a menudo.

La otra alternativa es una macro con-X, que establece las variables para su uso por el cuerpo de código:

(defmacro with-location [location & body] ; run body in location context 
    (concat 
    (list 'let ['{:keys [world country city building] :as location} `~location]) 
    `(~@body))) 

Example use: 
(with-location location (println city)) 

Entonces lo que hace el cuerpo, lo hace a la/país/ciudad/construcción del mundo establecido para y puede pasar todo a otra función usando el parámetro "pre-ensamblado" location.

Actualización: Ahora con una macro con ubicación que realmente funciona.

Answer 2

Trate

(update-in 
    world 
    [country city building] 
    (update-object-in-building object property value)) 

Answer 3

Una solución clásica de propósito general para este problema es lo que se llama "zipper" data structure. Hay una serie de variaciones, pero la idea básica es simple: dada una estructura de datos anidada, sáquela a medida que la recorre, de modo que en cada paso tenga un elemento "actual" y una lista de fragmentos que represente cómo reconstruir el resto de la estructura de datos "arriba" del elemento actual. Una cremallera puede quizás pensarse como un "cursor" que puede moverse a través de una estructura de datos inmutables, reemplazando las piezas a medida que avanza, recreando solo las partes que tiene que hacer.

En el caso trivial de una lista, los fragmentos son solo los elementos previos de la lista, almacenados en orden inverso, y el desplazamiento es simplemente mover el primer elemento de una lista a la otra.

En el caso no trivial pero aún simple de un árbol binario, cada fragmento consta de un valor y un subárbol, identificados como derecho o izquierdo. Mover la cremallera "abajo a la izquierda" implica agregar a la lista de fragmentos el valor del elemento actual y el secundario derecho, convirtiendo al niño izquierdo en el nuevo elemento actual. Mover "abajo a la derecha" funciona de manera similar, y mover "arriba" se hace combinando el elemento actual con el primer valor y el subárbol en la lista de fragmentos.

Si bien la idea básica de la cremallera es muy general, construir una cremallera para una estructura de datos específica generalmente requiere algunos bits especializados, tales como operaciones de construcción o cruce personalizado, para ser utilizados por una implementación de cremallera genérica.

El original paper describing zippers (advertencia, PDF) da un código de ejemplo en OCaml para una implementación que almacena fragmentos con una ruta explícita a través de un árbol. Como era de esperar, también se puede encontrar abundante material en cremalleras en Haskell. Como alternativa a la construcción de una ruta explícita y una lista de fragmentos, las cremalleras se pueden implementar in Scheme using continuations. Y finalmente, parece haber incluso un tree-oriented zipper provided by Clojure.