Manera idiomática de recurse a través de colecciones en Clojure

Question

Estoy tratando de entender cuál es la manera idiomática en Clojure para recurse a través de un árbol o una lista representada por una lista Clojure (u otro tipo de colección).

podría escribir lo siguiente para contar los elementos de una colección plana (ignorar el hecho de que no es recursiva de cola):

(defn length 
    ([xs] 
    (if (nil? (seq xs)) 
     0 
     (+ 1 (length (rest xs)))))) 

Ahora en Scheme o Cl todos los ejemplos sólo alguna vez hacer esto más listas , por lo que la prueba de caso base idiomática en esos idiomas sería (nil? xs). En Clojure, nos gustaría que esta función funcione en todos los tipos de colecciones, ¿cuál es la prueba idiomática (nil? (seq xs)), o quizás (empty? xs), o algo completamente diferente?

El otro caso que me gustaría considerar es el recorrido de árbol, es decir, atravesar una lista o un vector que representa un árbol, p. [1 2 [3 4].

Por ejemplo, contar los nodos en un árbol:

(defn node-count [tree] 
    (cond (not (coll? tree)) 1 
     (nil? (seq tree)) 0 
     :else (+ (node-count (first tree)) (node-count (rest tree))))) 

Aquí se utiliza para comprobar si hay (not (coll? tree)) átomos, mientras que en el Esquema/CL usaríamos atom?. También usamos (nil? (seq tree)) para verificar si hay una colección vacía. Y finalmente usamos first y rest para desestructurar el árbol actual a la rama izquierda y al resto del árbol.

Entonces, para resumir, son las siguientes formas idiomáticas en Clojure:

• (nil? (seq xs)) para detectar la colección vacía
• (first xs) y (rest xs) a excavar en la colección
• (not (coll? xs)) para comprobar si hay átomos

Answer 1

La prueba idiomática para un elemento no vacío es (seq coll):

(if (seq coll) 
    ... 
) 

El nil? es innecesaria, ya que un valor no nil regreso de seq se garantiza que sea un ss y por lo tanto no nil ni false y por lo tanto Truthy.

Si usted quiere tratar con el caso nil en primer lugar, se puede cambiar el if a if-not o seq a empty?; este último se implementa como una composición de seq con not (por lo que no es idiomático escribir (not (empty? xs)), consulte el docstring de empty?).

En cuanto a first/rest - es útil para recordar acerca de la variante estricta de rest, next, cuyo uso es más idiomático de envolver rest en un seq. Por último, coll? comprueba si su argumento es una colección persistente de Clojure (una instancia de clojure.lang.IPersistentCollection).Si esta es una verificación adecuada para "no-átomos" depende de si el código necesita manejar estructuras de datos Java como no-átomos (a través de interoperabilidad): p. (coll? (java.util.HashSet.)) es false, al igual que (coll? (into-array [])), pero puede llamar al seq en ambos. Hay una función llamada seqable? en core.incubator en el nuevo contrib modular que promete determinar si (seq x) tendría éxito para un x dado.

Answer 2

personalmente me gusta el siguiente enfoque a recursiva a través de una colección:

(defn length 
    "Calculate the length of a collection or sequence" 
    ([coll] 
    (if-let [[x & xs] (seq coll)] 
     (+ 1 (length xs)) 
     0))) 

Características:

• (SEC coll) es idiomático para comprobar que es una colección está vacía (como en gran respuesta de Michal)
• if-let con (seq coll) maneja automáticamente tanto la caja vacía como la vacía
• Puede usar destruc turing para nombrar la primera y siguientes elementos como desee para su uso en el cuerpo de la función

Tenga en cuenta que, en general, es mejor escribir funciones recursivas utilizando recur si es posible, para que usted obtenga los beneficios de la recursión de cola y don No corras el riesgo de explotar la pila. Así que con esto en mente, probablemente escribiría esta función específica de la siguiente manera:

(defn length 
    "Calculate the length of a collection or sequence" 
    ([coll] 
    (length coll 0)) 
    ([coll accumulator] 
    (if-let [[x & xs] (seq coll)] 
     (recur xs (inc accumulator)) 
     accumulator))) 

(length (range 1000000)) 
=> 1000000