clojure - concatenate - mapcat rompiendo la pereza

conj vector clojure

Question

Tengo una función que produce secuencias perezosas llamadas a-function.

Si ejecuto el código:

(map a-function a-sequence-of-values) 

devuelve una secuencia floja como se esperaba.

Pero cuando ejecuto el código:

(mapcat a-function a-sequence-of-values) 

rompe la pereza de mi función. De hecho, convierte ese código en

(apply concat (map a-function a-sequence-of-values)) 

Entonces necesita realizar todos los valores del mapa antes de concatenar esos valores.

Lo que necesito es una función que concatena el resultado de una función de mapa a pedido sin realizar todo el mapa de antemano.

Puedo hackear una función para esto:

(defn my-mapcat
  [f coll]
  (lazy-seq
   (if (not-empty coll)
     (concat
      (f (first coll))
      (my-mapcat f (rest coll))))))

Pero no puedo creer que Clojure no tenga algo hecho. ¿Sabes si clojure tiene esa característica? Solo unas pocas personas y yo tenemos el mismo problema?

También encontré un blog que trata el mismo tema: http://clojurian.blogspot.com.br/2012/11/beware-of-mapcat.html

Answer 1

Tu premisa es incorrecta. Concat es flojo, aplicar es flojo si su primer argumento es, y mapcat es flojo.

user> (class (mapcat (fn [x y] (println x y) (list x y)) (range) (range)))
0 0
1 1
2 2
3 3
clojure.lang.LazySeq

tenga en cuenta que se evalúan algunos de los valores iniciales (más sobre esto a continuación), pero claramente todo sigue siendo flojo (o la llamada nunca habría regresado, (range) devuelve una secuencia sin fin, y no volverá cuando se use ansiosamente).

El blog al que se vincula es sobre el peligro de utilizar mapcat de forma recurrente en un árbol diferido, porque está ansioso por los primeros elementos (que pueden sumarse en una aplicación recursiva).

Answer 2

La producción y el consumo de secuencia diferida es diferente de la evaluación perezosa.

Las funciones de Clojure hacen una evaluación estricta / entusiasta de sus argumentos. La evaluación de un argumento que es o que produce una secuencia perezosa no obliga a la realización de la secuencia floja producida en sí misma. Sin embargo, cualquier efecto secundario causado por la evaluación del argumento ocurrirá.

El caso de uso común para mapcat es concatenar secuencias producidas sin efectos secundarios. Por lo tanto, no importa que algunos de los argumentos sean evaluados con entusiasmo porque no se esperan efectos secundarios.

Su función my-mapcat impone una pereza adicional en la evaluación de sus argumentos al envolverlos en thunks (other lazy-seqs). Esto puede ser útil cuando se esperan efectos secundarios significativos: IO, consumo significativo de memoria, actualizaciones de estado. Sin embargo, las campanas de advertencia probablemente deberían estallar en tu cabeza si tu función está causando efectos secundarios y producir una secuencia para concatenar que tu código probablemente necesite refactorización.

Aquí es similar de algo.monads

(defn- flatten*
  "Like #(apply concat %), but fully lazy: it evaluates each sublist
   only when it is needed."
  [ss]
  (lazy-seq
    (when-let [s (seq ss)]
      (concat (first s) (flatten* (rest s))))))

Otra forma de escribir my-mapcat :

(defn my-mapcat [f coll] (for [x coll, fx (f x)] fx))

Aplicar una función a una secuencia perezosa forzará la realización de una parte de esa secuencia perezosa necesaria para satisfacer los argumentos de la función. Si esa función en sí misma produce secuencias perezosas como resultado, esas no se realizan como una cuestión de rutina.

Considere esta función para contar la porción realizada de una secuencia

(defn count-realized [s] 
  (loop [s s, n 0] 
    (if (instance? clojure.lang.IPending s)
      (if (and (realized? s) (seq s))
        (recur (rest s) (inc n))
        n)
      (if (seq s)
        (recur (rest s) (inc n))
        n))))

Ahora veamos qué se está realizando

(let [seq-of-seqs (map range (list 1 2 3 4 5 6))
      concat-seq (apply concat seq-of-seqs)]
  (println "seq-of-seqs: " (count-realized seq-of-seqs))
  (println "concat-seq: " (count-realized concat-seq))
  (println "seqs-in-seq: " (mapv count-realized seq-of-seqs)))          

 ;=> seq-of-seqs:  4
 ;   concat-seq:  0
 ;   seqs-in-seq:  [0 0 0 0 0 0]

Entonces, se realizaron 4 elementos del seq-de-seqs, pero ninguna de sus secuencias componentes se realizó ni hubo ninguna realización en la secuencia concatenada.

¿Por qué 4? Debido a que la versión sobrecargada arity aplicable de concat toma 4 argumentos [xy & xs] (cuente el & ).

Comparar con

(let [seq-of-seqs (map range (list 1 2 3 4 5 6))
      foo-seq (apply (fn foo [& more] more) seq-of-seqs)]
  (println "seq-of-seqs: " (count-realized seq-of-seqs))
  (println "seqs-in-seq: " (mapv count-realized seq-of-seqs)))

;=> seq-of-seqs:  2
;   seqs-in-seq:  [0 0 0 0 0 0]

(let [seq-of-seqs (map range (list 1 2 3 4 5 6))
      foo-seq (apply (fn foo [a b c & more] more) seq-of-seqs)]
  (println "seq-of-seqs: " (count-realized seq-of-seqs))
  (println "seqs-in-seq: " (mapv count-realized seq-of-seqs)))

;=> seq-of-seqs:  5
;   seqs-in-seq:  [0 0 0 0 0 0]

Clojure tiene dos soluciones para hacer la evaluación de los argumentos flojos.

Uno es macros. A diferencia de las funciones, las macros no evalúan sus argumentos.

Aquí hay una función con un efecto secundario

(defn f [n] (println "foo!") (repeat n n))

Los efectos secundarios se producen a pesar de que la secuencia no se realiza

user=> (def x (concat (f 1) (f 2)))
foo!
foo!
#''user/x
user=> (count-realized x)
0

Clojure tiene una macro de lazy-cat para evitar esto

user=> (def y (lazy-cat (f 1) (f 2)))
#''user/y
user=> (count-realized y)
0
user=> (dorun y)
foo!
foo!
nil
user=> (count-realized y)
3
user=> y
(1 2 2)

Desafortunadamente, no puedes apply una macro.

La otra solución para retrasar la evaluación es envolvente, que es exactamente lo que has hecho.