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

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

например. тип функции, которую я нашел (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)))))

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

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

Ответ 1

Есть два подхода, о которых я знаю:

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

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

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

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

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

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

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

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

Ответ 2

Попробуйте

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

Ответ 3

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

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

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

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

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