language-agnostic - orientada - programacion funcional ventajas y desventajas

Administrar actualizaciones de estructuras de datos inmutables anidadas en lenguajes funcionales

Question

Durante mi búsqueda de la programación funcional, me di cuenta de que hay casos en que las listas de parámetros comienzan a ser excesivas cuando se utilizan 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".

por ejemplo, el tipo de función que he encontrado escribiendo (ejemplo Clojure) 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 la persona que llama tiene que ensamblar todos los parámetros!

Este 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 conozco:

Recopila múltiples parámetros en algún tipo de objeto que sea conveniente pasar. 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 lo lleva a dos parámetros que la persona que llama necesita preocuparse (ubicación y atributo), lo cual puede ser justo si esos parámetros no cambian muy a menudo.

La otra alternativa es una macro con-X, que establece variables para que las use el cuerpo del 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, haga lo que haga el cuerpo, lo hace para el mundo / país / ciudad / edificio establecido para él, y puede pasar todo a otra función usando el parámetro de location "preensamblado".

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

Answer 2

Una solución clásica de propósito general para este problema es lo que se llama una estructura de datos "zipper" . 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 inmutable, 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 todavía simple de un árbol binario, cada uno de los fragmentos 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, la construcción de una cremallera para una estructura de datos específica generalmente requiere algunos bits especializados, como las operaciones de construcción u operaciones de cruce personalizadas, para ser utilizados por una implementación de cremallera genérica.

El documento original que describe las cremalleras (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 en Scheme usando continuaciones . Y finalmente, parece haber incluso una cremallera orientada a los árboles proporcionada por Clojure .

Answer 3

Tratar

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