Что такое идиоматические способ, чтобы добавить к вектору в Clojure?

добавление в список легко:

user=> (conj '(:bar :baz) :foo)
(:foo :bar :baz)

добавление к вектору легко:

user=> (conj [:bar :baz] :foo) 
[:bar :baz :foo]

как я (идиоматически) добавляю к вектору, возвращая вектор? Это не работает, поскольку он возвращает seq, а не вектор:

user=> (cons :foo [:bar :baz])     
(:foo :bar :baz)

это некрасиво (IMVHO):

user=> (apply vector (cons :foo [:bar :baz])) 
[:foo :bar :baz]

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

4 53
clojure vector adonetappender prepend

4 ответа:

векторы не предназначены для добавления. У вас есть только o(n) в вставить:

user=> (into [:foo] [:bar :baz])
[:foo :bar :baz]

то, что вы хотите, скорее всего, a дерево палец.

69

Я знаю, этот вопрос старый, но никто ничего не сказал о разнице списки и так как вы говорите, что вы действительно просто хотите что-то вы можете добавить и добавьте, похоже, что списки различий могут вам помочь. Они не кажутся популярными в Clojure, но они очень просты чтобы реализовать и намного менее сложные, чем пальцевые деревья, поэтому я сделал крошечная библиотека списка различий, только сейчас (и даже протестировала ее). Эти конкатенация в O (1) время (добавить или добавить). Преобразование разницы список обратно список должен стоить вам O (n), что является хорошим компромиссом, если вы делаете много конкатенаций. Если вы не делаете много конкатенация, тогда просто придерживайтесь списков, верно? :)

вот функции в этой крошечной библиотеке:

dl: список различий на самом деле является функцией, которая объединяет свои собственные содержимое с аргументом и возвращает результирующий список. Каждый раз вы создаете список различий, вы создаете небольшую функцию, которая действует как данные структура.

dlempty: так как список различий просто объединяет его содержимое с аргумент, пустой список различий-это то же самое, что и идентификатор функция.

undl: из-за того, что списки различий делают, вы можете конвертировать a список различий в обычный список, просто вызвав его с нулем, так что это функция не очень нужна, это просто для удобства.

dlcons: Cons-ячейки элемента к передней части списка -- не совсем необходимо, но экономия является достаточно распространенной операцией, и это просто один-лайнер (как и все функции, здесь).

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

Как сказал пользователь optevo в комментариях под ответом finger trees, вы можете использовать clojure / core.rrb-vector lib, который реализует rrb-деревья:

Rrb-деревья строятся на персистентных векторах Clojure, добавляя логарифмическую временную конкатенацию и нарезку. ClojureScript поддерживается с тем же API, за исключением отсутствия .

Я решил выложить это как отдельный ответ, потому что я думаю, что эта библиотека заслуживать тот. Он поддерживает ClojureScript и поддерживается Михал Marczyk, который довольно известен в сообществе Clojure за его работу по реализации различных структур данных.

2

Я бы предложил использовать функции удобства встроенный в библиотеку Tupelo. Например:

(append [1 2] 3  )   ;=> [1 2 3  ]
(append [1 2] 3 4)   ;=> [1 2 3 4]

(prepend   3 [2 1])  ;=> [  3 2 1]
(prepend 4 3 [2 1])  ;=> [4 3 2 1]

для сравнения, с raw Clojure легко ошибиться:

; Add to the end
(concat [1 2] 3)    ;=> IllegalArgumentException
(cons   [1 2] 3)    ;=> IllegalArgumentException
(conj   [1 2] 3)    ;=> [1 2 3]
(conj   [1 2] 3 4)  ;=> [1 2 3 4]

; Add to the beginning
(conj     1 [2 3] ) ;=> ClassCastException
(concat   1 [2 3] ) ;=> IllegalArgumentException
(cons     1 [2 3] ) ;=> (1 2 3)
(cons   1 2 [3 4] ) ;=> ArityException
2