vector - conj - cons clojure

¿Cuál es la forma idiomática de anteponer a un vector en Clojure?

Question

Anteponer a una lista es fácil:

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

Agregar a un vector es fácil:

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

¿Cómo prefiero (idiomáticamente) a un vector, mientras recupero un vector? Esto no funciona ya que devuelve un seq, no un vector:

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

Esto es feo (IMVHO):

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

Nota: Básicamente, solo quiero una estructura de datos a la que pueda anexar y anteponer. Anexar a listas grandes debería tener una gran penalización de rendimiento, así que pensé en vectores ...

Answer 1

Como dijo el usuario optevo en los comentarios debajo de la respuesta de los árboles, puedes usar el github.com/clojure/core.rrb-vector lib, que implementa RRB-trees:

RRB-Trees se basa en PersistentVectors de Clojure, agregando concatenación de tiempo logarítmico y slicing. ClojureScript es compatible con la misma API excepto por la ausencia de la función vector-of .

Decidí publicar esto como una respuesta separada, porque creo que esta biblioteca se merece eso. Es compatible con ClojureScript y lo mantiene Michał Marczyk , que es bastante conocido dentro de la comunidad de Clojure por su trabajo en la implementación de diversas estructuras de datos.

Answer 2

Los vectores no están diseñados para anteponerse. Usted solo tiene O (n) antes de:

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

Lo que quieres es muy probablemente un árbol de dedo .

Answer 3

Sé que esta pregunta es antigua, pero nadie dijo nada acerca de las listas de diferencias y, como dice que realmente solo quiere algo que pueda adjuntar y anexar, parece que las listas de diferencias podrían ayudarlo. No parecen populares en Clojure, pero son MUY fáciles de implementar y mucho menos complejos que los árboles de dedo, así que hice una pequeña biblioteca de listas de diferencias, justo ahora (e incluso lo probé). Estos se concatenan en tiempo O (1) (anteponer o anexar). La conversión de una lista de diferencias a una lista debería costar O (n), lo cual es una buena compensación si está haciendo mucha concatenación. Si no estás haciendo muchas concatenaciones, entonces simplemente mantente en las listas, ¿verdad? :)

Aquí están las funciones en esta pequeña biblioteca:

dl: una lista de diferencias es en realidad una función que concatena sus propios contenidos con el argumento y devuelve la lista resultante. Cada vez que produces una lista de diferencias, estás creando una pequeña función que actúa como una estructura de datos.

dlempty: como una lista de diferencias simplemente concatena su contenido con el argumento, una lista de diferencias vacía es lo mismo que la función de identidad.

undl: por lo que hacen las listas de diferencias, puede convertir una lista de diferencias en una lista normal simplemente llamándola con nil, por lo que esta función no es realmente necesaria; es solo por conveniencia.

dlcons: considera un elemento al principio de la lista; no es totalmente necesario, pero el uso es una operación bastante común y es solo una línea (como todas las funciones, aquí).

dlappend: concatena dos listas de diferencias. Creo que su definición es la más divertida. ¡Compruébalo! :)

Y ahora, aquí está esa pequeña biblioteca: 5 funciones de una línea que le dan una estructura de datos O (1) para añadir / anteponer. No está mal, ¿eh? Ah, la belleza del cálculo de Lambda ...

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

Puedes verlo en acción con esto:

(undl (dlappend (dl ''(1 2 3)) (dl ''(4 5 6))))

que devuelve:

(1 2 3 4 5 6)

Esto también devuelve lo mismo:

((dl ''(1 2 3)) ''(4 5 6))

Diviértete con listas de diferencias!

Actualizar

Aquí hay algunas definiciones que pueden ser más difíciles de entender, pero creo que son mejores:

(defn dl [& elements] (fn [x] (concat elements x)))
(defn dl-un [l] (l nil))
(defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))

Esto te permite decir algo como esto:

(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))

Cuál regresaría

(1 2 3 4)

Answer 4

Sugiero usar las características de conveniencia integradas en la Biblioteca Tupelo . Por ejemplo:

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

en comparación, con Clojure crudo es fácil cometer un error:

; 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