Clojure: reducción, reducciones y listas infinitas

Question

Reduce y las reducciones le permiten acumular el estado en una secuencia. Cada elemento en la secuencia modificará el estado acumulado hasta el al final de la secuencia se alcanza.

¿Cuáles son las implicaciones de reducir llamadas o reducciones en una lista infinita?

(def c (cycle [0])) 
(reduce + c) 

Esto arrojará rápidamente un OutOfMemoryError. Por cierto, (reduce + (cycle [0])) no arroja un OutOfMemoryError (al menos no por el tiempo que esperé). Nunca regresa No estoy seguro por qué.

¿Hay alguna manera de llamar a reducción o reducciones en una lista infinita de una manera que tenga sentido? El problema que veo en el ejemplo anterior es que, finalmente, la parte evaluada de la lista se vuelve lo suficientemente grande como para desbordar el montón. Tal vez una lista infinita no es el paradigma correcto. La reducción de un generador, secuencia de E/S o una secuencia de eventos tendría más sentido. El valor no debe mantenerse después de que se haya evaluado y utilizado para modificar el estado.

Answer 1

Nunca volverá porque reduce toma una secuencia y una función y aplica la función hasta la secuencia de entrada está vacía, solo entonces puede saber que tiene el valor final.

Reducir en un seq verdaderamente infinito no tendría mucho sentido a menos que esté produciendo un efecto secundario como registrar su progreso.

En su primer ejemplo, primero está creando una var haciendo referencia a una secuencia infinita.

(def c (cycle [0])) 

Luego está pasando el contenido de la var c para reducir el que comienza a leer elementos para actualizar su estado.

(reduce + c) 

Estos elementos no se pueden basura recogieron porque el var c contiene una referencia a la primera de ellas, que a su vez contiene una referencia a la segunda y así sucesivamente. Eventualmente lee tantas como espacio hay en el montón y luego OOM.

Para evitar explotar el montón en su segundo ejemplo, no está guardando una referencia a los datos que ya ha utilizado para que los elementos en el seq devuelto por ciclo sean GCd tan rápido como se producen y el resultado acumulado continúa aumentar de tamaño. Con el tiempo se hubiera sobrepasado un accidente de largo y (clojure 1.3) o promocionarse a un BigInteger y crecer hasta el tamaño de toda la pila (clojure 1,2)

(reduce + (cycle [0])) 

Answer 2

respuesta de Arthur es bueno en lo que cabe, pero parece que no aborda su segunda pregunta sobre reductions. reductions devuelve una secuencia perezosa de etapas intermedias de lo que reducehabría habría devuelto si se le hubiera dado una lista de solo N elementos de longitud. Así que es perfectamente razonable para llamar reductions en una lista infinita:

user=> (take 10 (reductions + (range))) 
(0 1 3 6 10 15 21 28 36 45) 

Answer 3

Si desea seguir recibiendo los artículos en una lista como una corriente IO y mantener el estado entre las corridas, no se puede utilizar doseq (sin recurrir a def 's).En lugar de un buen enfoque sería utilizar bucle/reaparecer que esto permitirá evitar consumir demasiado espacio en la pila y le permitirá mantener el estado, en su caso:

(loop [c (cycle [0])] 
    (if (evaluate-some-condition (first c)) 
    (do-something-with (first c) (recur (rest c))) 
    nil)) 

Por supuesto, en comparación con el caso de que haya aquí una verificación de condición para asegurarse de que no bucle indefinidamente.

Answer 4

Como han señalado otros, no tiene sentido ejecutar reducir directamente en una secuencia infinita, ya que reduce no es vago y necesita consumir la secuencia completa.

Como una alternativa para este tipo de situación, aquí es una función muy útil que reduce sólo los primeros n elementos en una secuencia, implementado usando repiten para una eficiencia razonable:

(defn counted-reduce 
    ([n f s] 
    (counted-reduce (dec n) f (first s) (rest s))) 
    ([n f initial s] 
    (if (<= n 0) 
     initial 
     (recur (dec n) f (f initial (first s)) (rest s))))) 

(counted-reduce 10000000 + (range)) 
=> 49999995000000