¿Cómo evito el comportamiento de fragmentación de Clojure para los seqs perezosos que quiero cortocircuitar?

chunking lazy-sequences

Question

Tengo una secuencia larga y lenta que quiero reducir y probar perezosamente. Tan pronto como dos elementos secuenciales no son = (o algún otro predicado) entre sí, quiero dejar de consumir la lista, que es costoso de producir. Sí, esto suena como take-while , pero sigue leyendo.

Quería escribir algo simple y elegante como este (fingiendo por un minuto que every? funciona como reduce ):

(every? = (range 100000000))

Pero eso no funciona perezosamente, por lo que se cuelga en infinitos momentos. Descubrí que esto funciona casi como yo quería:

(apply = (range 100000000))

Sin embargo, noté que la fragmentación de secuencias estaba generando y probando elementos extra e innecesarios. Al menos, esto es lo que creo que esto es lo que sucede en el siguiente fragmento de código:

;; Displays chunking behavior in groups of four on my system and prints 1 2 3 4
(apply = (map #(do (println %) %) (iterate inc 1)))

;; This prints 0 to 31
(apply = (map #(do (println %) %) (range)))

Encontré una solución usando take-while , y count para verificar el número de elementos tomados, pero eso es bastante engorroso.

¿Debo sugerir educadamente a Rich Hickey que haga una combinación de reduce y every? cortocircuito correctamente, ¿o me falta alguna forma obvia que ya existe?

EDITAR: Dos personas amables publicaron soluciones para evitar fragmentar las secuencias perezosas, pero ¿cómo evito fragmentar cuando hago la apply , que parece estar consumiendo en grupos de cuatro?

EDICION # 2: Como señala Stuart Sierra y descubrí de forma independiente, esto no se está fragmentando. Es solo aplicar actuando normalmente, así que lo llamaré cerrado y le daré la respuesta. Incluí una pequeña función en una respuesta separada para hacer la parte de reducción del problema, para aquellos que estén interesados.

Answer 1

Buscar en clojure.core en la definición de aplicar hace que sea obvio por qué se fragmentaba en grupos de cuatro cuando se usa apply con una secuencia infinita. Reduce no cortocircuito, tampoco ... entonces me queda escribir mi propia solución:

(defn reducep
  "Like reduce, but for use with a predicate. Short-circuits on first false."
  ([p coll]
     (if-let [s (seq coll)]
       (reducep p (first s) (next s))
       (p)))
  ([p val coll]
     (if-let [s (seq coll)]
       (if-let [v (p val (first s))]
         (recur p (first s) (next s))
         false)
       true)))

Luego, usando el unchunk de Stuart (con un extra and )

(defn unchunk [s]
  (lazy-seq
   (cons (first s)
         (and (next s)
              (unchunk (next s))))))

Yo obtengo:

(reducep = (map #(do (print %) %) (unchunk (range)))) ;; Prints 01, returns false
(reducep = (map #(do (print %) %) (repeat 20 1))) ;; returns true
(reducep = (map #(do (print %) %) (unchunk [0 0 2 4 5]))) ;; Returns false
(reducep = (map #(do (print %) %) (unchunk [2 2 2 2 2]))) ;; returns true

Si eso también funciona para ti, modifícalo.

EDITAR : La versión modificada de Stuart de unchunk después de su edición es probablemente preferible a la de esta publicación anterior.

Answer 2

Encontré esta publicación al llegar a un límite de tiempo en un problema de 4clojure y encontré otra forma de evitar los 32 bits:

;; add another dummy sequence parameter to the map:
(apply = (map #(do (prn %2) %) (range) (range)))

Las formas de aria superiores del mapa no parecen usar secuencias fragmentadas (clojure 1.5)

Tienes que hacer algo con el segundo parámetro, por lo que ser explícito sobre eso podría ser mejor:

(apply = (map (fn [i _] (prn i) i) (range) (range)))

Esto no es tan limpio como las otras soluciones, pero podría ser útil para usos rápidos y sucios, como la prueba "¿es lento debido a la fragmentación?".

Con respecto a apply , puedes usar partition para obtener pares de la secuencia y = them:

(every? #(apply = %) (partition 2 1
    (map (fn [i _] (prn i) i) (range) (range))))

Aunque reducep parece útil.

PD. No quiero dar la impresión de que la secuencia fragmentada es más lenta, no lo es. Mi problema es que el caso de prueba 4clojure llama "primero" a mi función de generación de seq en un rango de valores, por lo que dividir en pedazos significa que hago 32 veces el trabajo. (PPS. Mi código es demasiado lento)

Answer 3

DOS VECES CORREGIDO: una forma más simple de deshacer una secuencia floja:

(defn unchunk [s]
  (when (seq s)
    (lazy-seq
      (cons (first s)
            (unchunk (next s))))))

Primera versión omitida (when ... así que devolvió un seq infinito de nil después de que la secuencia de entrada finalizó.

La segunda versión se usó first lugar de seq por lo que se detuvo en cero.

RE: su otra pregunta, "¿cómo evito fragmentar al hacer la aplicación, que parece consumir en grupos de cuatro" ?

Esto se debe a la definición de = , que, cuando se le da una secuencia de argumentos, fuerza a los primeros 4:

(defn =
  ;; ... other arities ...
  ([x y & more]
   (if (= x y)
     (if (next more)
       (recur y (first more) (next more))
       (= y (first more)))
     false)))