Gestion des mises à jour des structures de données immuables imbriquées dans les langages fonctionnels

Question

Lors de mes recherches sur la programmation fonctionnelle, j'ai remarqué qu'il y a des cas où les listes de paramètres commencent à devenir excessives lors de l'utilisation de structures de données immuables imbriquées. Cela est dû au fait que lors de la mise à jour d'un état d'objet, vous devez également mettre à jour tous les nœuds parents dans la structure de données. Notez que je prends ici "mise à jour" pour signifier "retourner un nouvel objet immuable avec le changement approprié".

par exemple. le genre de fonction que j'ai trouvé écrit moi-même (par exemple Clojure) est:

(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))))) 

Tout cela pour mettre à jour une propriété simple est assez laid, mais en plus l'appelant doit rassembler tous les paramètres!

Cela doit être une exigence assez courante lorsque vous traitez des structures de données immuables dans les langages fonctionnels en général, alors y a-t-il un bon schéma ou une astuce pour éviter cela que je devrais utiliser à la place?

Answer 1

Il existe deux approches que je connais:

Collect plusieurs paramètres dans une sorte d'objet qui est pratique pour passer autour. Exemple:

; 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))) 

Cela vous amène jusqu'à deux paramètres que l'appelant a besoin de se soucier (emplacement et attribut), qui peut être assez juste si ces paramètres ne changent pas très souvent.

L'autre alternative est un avec-X macro, qui définit les variables utilisées par le corps de code:

(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)) 

Ensuite, quel que soit le corps fait, il le fait dans le monde/pays/ville/bâtiment situé pour et il peut passer le tout à une autre fonction en utilisant le "pré-assemblé" location paramètre.

Mise à jour: Maintenant, avec une macro d'emplacement qui fonctionne réellement.

Answer 2

Essayez

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

Answer 3

Une solution universelle classique à ce problème est ce qu'on appelle un "zipper" data structure. Il y a un certain nombre de variations, mais l'idée de base est simple: Étant donné une structure de données imbriquée, démontez-la pendant que vous la traversez, de sorte qu'à chaque étape vous avez un élément "courant" et une liste de fragments reste de la structure de données "au-dessus" de l'élément en cours. Une fermeture à glissière peut peut-être être considérée comme un «curseur» qui peut se déplacer dans une structure de données immuable, en remplaçant les pièces au fur et à mesure, en ne recréant que les parties dont elle a besoin.

Dans le cas trivial d'une liste, les fragments sont simplement les éléments précédents de la liste, stockés dans l'ordre inverse, et la traversée déplace simplement le premier élément d'une liste à l'autre.

Dans le cas non trivial mais toujours simple d'un arbre binaire, les fragments sont constitués chacun d'une valeur et d'un sous-arbre, identifiés comme étant à droite ou à gauche. Le déplacement de la fermeture à glissière «bas-gauche» implique l'ajout à la liste des fragments de la valeur de l'élément courant et de l'enfant à droite, faisant de l'enfant à gauche le nouvel élément courant. Déplacer "vers la droite" fonctionne de la même façon, et déplacer "vers le haut" est fait en combinant l'élément courant avec la première valeur et la sous-arborescence de la liste des fragments.Bien que l'idée de base de la fermeture à glissière soit très générale, la construction d'une fermeture à glissière pour une structure de données spécifique nécessite généralement l'utilisation de bits spécialisés, tels que des opérations de traversée ou de construction personnalisées.

Le original paper describing zippers (avertissement, PDF) donne un exemple de code dans OCaml pour une implémentation stockant des fragments avec un chemin explicite à travers une arborescence. Sans surprise, beaucoup de matériel peut également être trouvé sur les fermetures à glissière dans Haskell. Comme alternative à la construction d'une liste explicite de chemins et de fragments, les fermetures à glissière peuvent être implémentées in Scheme using continuations. Et enfin, il semble même être un tree-oriented zipper provided by Clojure.