Partycjonowanie seq - Rekursja w Clojure (lub Lisp w ogóle)

Question

W projekcie nad którym pracuję natknąłem się na interesujący problem, który mnie interesuje z innymi rozwiązaniami. Jestem w trakcie czytania "The Little Schemer", więc wypróbowuję niektóre techniki rekursji. Zastanawiam się, czy istnieje inny sposób, aby to zrobić z rekursją, a także zainteresowany, jeśli istnieje podejście bez użycia rekursji.

Problem polega na wykonaniu sekwencji i podzieleniu jej na seqs seqs, biorąc co n-ty element. Na przykład ten wektor:

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

gdy podzielono między n = 3 będzie produkować Seq

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

o N = 4:

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

i tak dalej. Rozwiązałem to za pomocą dwóch funkcji. Pierwszy tworzy wewnętrzne seqs, a drugi ściąga je razem. Oto moje funkcje:

(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)))))) 

nie jestem całkowicie zadowolony z funkcją partycja-po-n-ty posiadającej wiele arity prostu dla rekursji, ale nie widział innego sposobu.

Wygląda na to, że działa dobrze we wszystkich przypadkach testowych. Czy to przyzwoite podejście? Czy to zbyt skomplikowane? Czy istnieje sposób, aby to zrobić bez rekurencji, a może w jednej funkcji rekurencyjnej?

Dzięki za sugestie. Jestem nowy zarówno dla Clojure'a, jak i Lispa, więc podchodzę do różnych technik.

Answer 1

Spodziewam jest prostsze rekurencyjna definicja, która jest bardziej w duchu Mała Schemer, ale następująca funkcja za pomocą take-nth jest trochę bardziej kompaktowy, ponieważ powiedział, że jesteś zainteresowany alternatywnymi podejściami:

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

który spełnia swoje przykłady:

(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)) 

w Clojure, wbudowany w bibliotekach będzie ci zaskakująco daleko; gdy to się nie powiedzie, użyj jawnie rekurencyjnego rozwiązania. Ta wersja jest również leniwy; prawdopodobnie będziesz chciał użyć lazy-seq lub loop...recur w dowolnej wersji "longhandowej" (jawnie rekurencyjnej) do obsługi dużych zestawów danych bez dmuchania stosu.

Answer 2

Edytowane, ponieważ oryginalna odpowiedź całkowicie pomijała punkt.

Kiedy po raz pierwszy zobaczyłem to pytanie, uznałem, że zastosowano funkcję clojure.core partition (patrz ClojureDocs page).

Jak zauważył Dave partycja działa tylko na elementach w pierwotnej kolejności. Rozwiązanie take-nth jest wyraźnie lepsze. Tylko ze względu na zainteresowanie połączenie mapy z wieloma sekwencjami wywodzącymi się z rodzajów działek.

(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

Mam do zaoferowania ten Common Lisp pętlę:

(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))))