Управление обновлениями вложенных неизменных структур данных на функциональных языках
Я заметил, в то время как на моих поисках для склонности функционального программирования, что существуют случаи, когда списки параметров начинают становиться чрезмерными, когда использование вложило неизменные структуры данных. Это вызвано тем, что при создании обновления объектного состояния, необходимо обновить все родительские узлы в структуре данных также. Обратите внимание, что здесь я беру "обновление" для значения, "возвращают новый неизменный объект с соответствующим изменением".
например, вид функции, которую я писал (пример 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)))))
Все это для обновления одного простого свойства довольно ужасно, но кроме того вызывающая сторона должна собрать все параметры!
Это должно быть довольно общим требованием при контакте с неизменными структурами данных на функциональных языках обычно, так там хороший шаблон или прием для предотвращения этого, что я должен использовать вместо этого?
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 действительно работает.
Попробуйте
(update-in
world
[country city building]
(update-object-in-building object property value))
Классическим решением этой проблемы общего назначения является так называемая "молниевая" структура данных. Существует множество вариаций, но основная идея проста: Учитывая вложенную структуру данных, разбирайте ее по мере прохождения, так чтобы на каждом шаге у вас был "текущий" элемент и список фрагментов, представляющих, как восстановить остальную часть структуры данных "над" текущим элементом. Возможно, молнию можно представить как "курсор", который может перемещаться по неизменяемой структуре данных, заменяя фрагменты по мере прохождения, воссоздавая только те части, которые необходимо.
В тривиальном случае списка, фрагменты - это просто предыдущие элементы списка, сохраненные в обратном порядке, а обход - это просто перемещение первого элемента одного списка в другой.
В нетривиальном, но все еще простом случае бинарного дерева, фрагменты состоят из значения и поддерева, идентифицируемого как правое или левое. Перемещение молнии "вниз-влево" включает добавление в список фрагментов значения текущего элемента и его правого дочернего элемента, в результате чего левый дочерний элемент становится новым текущим элементом. Перемещение "вниз-вправо" работает аналогично, а перемещение "вверх" выполняется путем объединения текущего элемента с первым значением и поддеревом в списке фрагментов.
Хотя основная идея молнии очень общая, построение молнии для конкретной структуры данных обычно требует некоторых специализированных битов, таких как пользовательские операции обхода или построения, для использования общей реализацией молнии.
В оригинальной статье, описывающей молнии (предупреждение, PDF), приводится пример кода на OCaml для реализации, хранящей фрагменты с явным путем по дереву. Неудивительно, что много материала по молниям можно найти и в Haskell. В качестве альтернативы построению явного пути и списка фрагментов, молнии могут быть реализованы в Scheme с использованием продолжений. И, наконец, похоже, что в Clojure даже существует древовидно-ориентированная молния.