clojure cons vs conj con perezoso-seq

conj vector clojure

Question

¿Por qué los inconvenientes funcionan en este contexto con lazy-seq, pero conj no?

Esto funciona:

(defn compound-interest [p i]
(cons p (lazy-seq (compound-interest (* p (+ 1 i)) i))))

Esto no (da una excepción de desbordamiento de pila [1]):

(defn compound-interest2 [p i]
(conj (lazy-seq (compound-interest2 (* p (+ 1 i)) i)) p))

[1] ¡Oh, ya! Hacer una pregunta que involucra un desbordamiento de pila en stackoverflow.

Answer 1

(conj collection item) agrega item a la collection . Para hacer eso, necesita realizar la collection . (Explicaré por qué a continuación.) Por lo tanto, la llamada recursiva ocurre de inmediato, en lugar de posponerse.

(cons item collection) crea una secuencia que comienza con el item , seguido de todo en la collection . Significativamente, no es necesario realizar la collection . Entonces, la llamada recursiva se aplazará (debido al uso de lazy-seq ) hasta que alguien intente obtener la cola de la secuencia resultante.

Explicaré cómo funciona esto internamente:

cons devuelve realmente un objeto clojure.lang.Cons , que es de lo que están hechas las secuencias perezosas. conj devuelve el mismo tipo de colección que la pasa (ya sea una lista, un vector o cualquier otra cosa). conj hace esto usando una llamada de método polimórfico Java en la colección en sí. (Vea la línea 524 de clojure/src/jvm/clojure/lang/RT.java ).

¿Qué sucede cuando ocurre esa llamada al método Java en el objeto clojure.lang.LazySeq que devuelve lazy-seq ? (La forma en que los objetos LazySeq y LazySeq funcionan juntos para formar secuencias perezosas se LazySeq más adelante). Mire la línea 98 de clojure/src/jvm/clojure/lang/LazySeq.java . Observe que llama a un método llamado seq . Esto es lo que se da cuenta del valor de LazySeq (salte a la línea 55 para más detalles).

Entonces, podrías decir que el conj necesita saber exactamente qué tipo de colección lo pasaste, pero los cons no lo hacen. cons solo requiere que el argumento "colección" sea un ISeq .

Tenga en cuenta que los objetos Cons en Clojure son diferentes de las "células cons" en otros Lisps: en la mayoría de Lisps, un "contra" es simplemente un objeto que contiene 2 punteros a otros objetos arbitrarios. De modo que puede usar células de cons para construir árboles, y así sucesivamente. Un Clojure Cons toma un Object arbitrario como cabeza, y un ISeq como cola. Dado que los propios Cons implementan ISeq , puede construir secuencias a partir de objetos Cons , pero también pueden indicar vectores, listas, etc. (Tenga en cuenta que una "lista" en Clojure es un tipo especial (Lista PersistentList ) y no es construido a partir de objetos Cons .) clojure.lang.LazySeq también implementa ISeq , por lo que se puede usar como la cola ("cdr" en Lisps) de un Cons . Un LazySeq contiene una referencia a algún código que evalúa a un ISeq de algún tipo, pero en realidad no evalúa ese código hasta que sea necesario, y después de que evalúa el código, almacena en caché el ISeq devuelto y lo delega.

... ¿todo esto empieza a tener sentido? ¿Tienes la idea de cómo funcionan las secuencias perezosas? Básicamente, comienzas con un LazySeq . Cuando se realiza LazySeq , se evalúa como un Cons , que apunta a otro LazySeq . Cuando ese se realiza ... entiendes la idea. Entonces obtienes una cadena de objetos de LazySeq , cada tenencia (y delegación) de un Cons .

Acerca de la diferencia entre "conses" y "listas" en Clojure, "listas" (objetos PersistentList ) contienen un campo de "longitud" en caché, por lo que pueden responder para count en O (1) vez. Esto no funcionaría en otros Lisps, porque en la mayoría de Lisps, las "listas" son mutables. Pero en Clojure son inmutables, por lo que el almacenamiento en caché funciona.

Cons objetos Cons en Clojure no tienen una longitud de caché; si lo hicieran, ¿cómo podrían usarse para implementar secuencias perezosas (e incluso infinitas)? Si intentas count el count de Cons , solo count en su cola, y luego incrementa el resultado en 1.