Я знаю, что этот вопрос старый, но никто ничего не сказал о разнице
списки и так как вы говорите, что вы действительно хотите что-то добавить
и, прежде всего, кажется, что списки различий могут вам помочь.
Они не кажутся популярными в Clojure, но они ОЧЕНЬ легки
реализовать и намного менее сложный, чем пальчиковые деревья, поэтому я сделал
крошечная библиотека списков различий, только сейчас (и даже проверенная). Эти
объединить в O (1) времени (добавить или добавить). Преобразование разницы
список обратно к списку должен стоить вам O (n), что является хорошим компромиссом, если
вы делаете много конкатенации. Если вы не делаете много
объединение, а затем просто придерживаться списков, верно? :)
Вот функции в этой крошечной библиотеке:
dl: Список различий на самом деле является функцией, которая объединяет свои собственные
содержимое с аргументом и возвращает результирующий список. Каждый раз
вы создаете список различий, вы создаете небольшую функцию, которая
действует как структура данных.
dlempty: Поскольку список различий просто объединяет свое содержимое с
аргумент, пустой список различий совпадает с идентичностью
функция.
undl: Из-за того, что делают списки различий, вы можете конвертировать
список различий к обычному списку, просто вызвав его с нулем, так что это
функция на самом деле не нужна; это просто для удобства.
dlcons: помещает элемент в начало списка - не полностью
необходимо, но консинг является достаточно распространенной операцией, и это просто
одна строка (как и все функции, здесь).
dlappend: объединяет два списка различий. Я думаю, что его определение
самое веселое - зацени! :)
А теперь вот эта крошечная библиотека - 5 однострочных функций, которые дают вам O (1)
добавить / добавить структуру данных. Неплохо, а? Ах, красота лямбды
Исчисление ...
(defn dl
"Return a difference list for a list"
[l]
(fn [x] (concat l x)))
; Return an empty difference list
(def dlempty identity)
(defn undl
"Return a list for a difference list (just call the difference list with nil)"
[aDl]
(aDl nil))
(defn dlcons
"Cons an item onto a difference list"
[item aDl]
(fn [x] (cons item (aDl x))))
(defn dlappend
"Append two difference lists"
[dl1 dl2]
(fn [x] (dl1 (dl2 x))))
Вы можете увидеть это в действии с помощью:
(undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))
, который возвращает:
(1 2 3 4 5 6)
Это также возвращает то же самое:
((dl '(1 2 3)) '(4 5 6))
Получайте удовольствие от списков различий!
Обновление
Вот некоторые определения, которые могут быть более трудными для понимания, но я думаю, что они лучше:
(defn dl [& elements] (fn [x] (concat elements x)))
(defn dl-un [l] (l nil))
(defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))
Это позволяет вам сказать что-то вроде этого:
(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))
Что вернет
(1 2 3 4)