Управление обновлениями вложенных неизменяемых структур данных на функциональных языках

Question

Я заметил, что в моем стремлении использовать функциональное программирование существуют случаи, когда списки параметров становятся чрезмерными при использовании вложенных неизменяемых структур данных.Это связано с тем, что при обновлении состояния объекта необходимо также обновить все родительские узлы в структуре данных.Обратите внимание, что здесь я принимаю «обновить», чтобы означать «вернуть новый неизменный объект с соответствующим изменением».

например, вид функции, которую я написал (пример Clojure):

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

Все это для обновления одного простого свойства довольно уродливо, но, кроме того, вызывающая сторона должна собрать все параметры!

Это должно быть довольно распространенным требованием при работе с неизменяемыми структурами данных в функциональных языках,так есть ли хороший шаблон или хитрость, чтобы избежать этого, что я должен использовать вместо этого?

Answer 1

Попробуйте

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

Answer 2

Классическим универсальным решением этой проблемы является то, что называется структура данных "застежка-молния" .Существует несколько вариантов, но основная идея проста: учитывая вложенную структуру данных, разбирайте ее по мере прохождения, чтобы на каждом шаге у вас был «текущий» элемент и список фрагментов, представляющих, как восстановитьОстальная часть структуры данных «выше» текущего элемента.Застежка-молния, возможно, может рассматриваться как «курсор», который может перемещаться по неизменной структуре данных, заменяя части по мере необходимости, воссоздавая только те части, которые ему необходимы.

В тривиальном случае спискафрагменты - это просто предыдущие элементы списка, хранящиеся в обратном порядке, а обход - просто перемещение первого элемента одного списка в другой.

В нетривиальном, но все же простом случае двоичного дерева фрагментыкаждый состоит из значения и поддерева, идентифицированного как правое или левое.Перемещение молнии «вниз-влево» включает в себя добавление к списку фрагментов значения текущего элемента и правого дочернего элемента, делая левый дочерний элемент новым текущим элементом.Перемещение «вниз-вправо» работает аналогично, а перемещение «вверх» осуществляется путем объединения текущего элемента с первым значением и поддеревом в списке фрагментов.

Хотя основная идея молнии очень общая, построениеЗастежка-молния для конкретной структуры данных обычно требует использования специальных битов, таких как пользовательские операции обхода или конструирования, для реализации универсальной молнии.

Оригинальный документ , описывающий застежки-молнии (предупреждение,PDF) приводит пример кода в OCaml для реализации, хранящей фрагменты с явным путем через дерево.Неудивительно, что на молнии в Haskell также можно найти много материала.В качестве альтернативы построению явного пути и списка фрагментов молнии могут быть реализованы на схеме , используя продолжения .И, наконец, кажется, есть даже ориентированная на дерево молния, предоставленная Clojure .

Answer 3

Мне известны два подхода:

Собрать несколько параметров в каком-либо объекте, который удобно обойти.Пример:

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

Это сводит вас к двум параметрам, которые необходимо учитывать вызывающей стороне (местоположение и атрибут), что может быть достаточно справедливым, если эти параметры меняются не очень часто.

Другой альтернативой является макрос with-X, который устанавливает переменные для использования телом кода:

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

Тогда, что бы тело ни делало, оно делает с набором мира / страны / города / здания для негои он может передать всю вещь другой функции, используя «предварительно собранный» параметр location.

Обновление : теперь с макросом with-location, который действительно работает.