Particionado de una secuencia - Recursividad en Clojure (o Lisp en general)

Question

En un proyecto en el que estoy trabajando me encontré con un problema interesante que me llama la atención sobre otras soluciones. Estoy leyendo "The Little Schemer", así que estoy probando algunas técnicas de recursión. Me pregunto si hay otra manera de hacer esto con la recursión y también me interesa si hay un enfoque sin usar la recursión.

El problema es tomar una secuencia y dividirla en un seqs de secos tomando cada elemento enésimo. Por ejemplo, este vector:

[ :a :b :c :d :e :f :g :h :i ] 

cuando se repartió con n = 3 produciría la SEC

((:a :d :g) (:b :e :h) (:c :f :i)) 

y con n = 4:

((:a :e :i) (:b :f) (:c :g) (:d :h)) 

y así sucesivamente. Lo resolví usando dos funciones. El primero crea los seqs internos y el otro los une. Aquí están mis funciones:

(defn subseq-by-nth 
    "Creates a subsequence of coll formed by starting with the kth element and selecting every nth element." 
    [coll k n] 
    (cond (empty? coll) nil 
     (< (count coll) n) (seq (list (first coll))) 
     :else (cons (nth coll k) (subseq-by-nth (drop (+ n k) coll) 0 n)))) 

(defn partition-by-nth 
    "" 
    ([coll n] 
    (partition-by-nth coll n n)) 
    ([coll n i] 
     (cond (empty? coll) nil 
     (= 0 i) nil 
     :else (cons (subseq-by-nth coll 0 n) (partition-by-nth (rest coll) n (dec i)))))) 

No estoy completamente satisfecho con la función de partición por enésima tener múltiples aridad simplemente por la recursividad, pero no podía ver otra manera.

Esto parece funcionar bien con todos los casos de prueba. ¿Es este un enfoque decente? ¿Es demasiado complicado? ¿Hay alguna manera de hacer esto sin recurrencia o tal vez en una sola función recursiva?

Gracias por las sugerencias. Soy nuevo en Clojure y Lisp, así que estoy aprendiendo las diferentes técnicas sobre la marcha.

Answer 1

espero que hay una definición recursiva más simple que es más en el espíritu de El pequeño Schemer, pero la siguiente función usando take-nth es un poco más compacto, ya que dijo que estaban interesados ​​en los enfoques alternativos:

(defn chop [coll n] 
    (for [i (range n)] 
    (take-nth n (drop i coll)))) 

que satisface sus ejemplos:

(chop [:a :b :c :d :e :f :g :h :i ] 3) 
;= ((:a :d :g) (:b :e :h) (:c :f :i)) 

(chop [:a :b :c :d :e :f :g :h :i ] 4) 
;= ((:a :e :i) (:b :f) (:c :g) (:d :h)) 

en Clojure, el construido en bibliotecas le conseguirá sorprendentemente lejos; cuando eso falla, use una solución explícitamente recursiva. Esta versión también es floja; es probable que desee utilizar lazy-seq o loop...recur en cualquier versión "a mano" (explícitamente recursiva) para manejar grandes conjuntos de datos sin soplar la pila.

Answer 2

Editado porque la respuesta original olvidó por completo el punto.

Cuando vi esta pregunta por primera vez, pensé que se aplicaba la función clojure.core partition (consulte ClojureDocs page).

Como señaló Dave, la partición solo funciona en los elementos en el orden original. La solución take-nth es claramente mejor. Solo por el bien de una combinación de mapas con múltiples secuencias derivadas de trabajos tipo partición.

(defn ugly-solution [coll n] 
    (apply map list (partition n n (repeat nil) coll))) 

(ugly-solution [:a :b :c :d :e :f :g :h :i] 3) 
;;=> ((:a :d :g) (:b :e :h) (:c :f :i)) 
(ugly-solution [:a :b :c :d :e :f :g :h :i] 4) 
;;=> ((:a :e :i) (:b :f nil) (:c :g nil) (:d :h nil)) 

Answer 3

que tengo que ofrecer este bucle Common Lisp:

(defun partition-by-nth (list n) 
    (loop :with result := (make-array n :initial-element '()) 
     :for i :upfrom 0 
     :and e :in list 
     :do (push e (aref result (mod i n))) 
     :finally (return (map 'list #'nreverse result))))