Partitioning a seq - Recursion in Clojure (or Lisp in general)

Question

In a project I'm working on I came across an interesting problem that I'm curious about other solutions for. I'm in the middle of reading "The Little Schemer" so I'm trying out some recursion techniques. I'm wondering if there is another way to do this with recursion and also interested if there is an approach without using recursion.

The problem is to take a sequence and partition it into a seq of seqs by taking every nth element. For example this vector:

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

when partitioned with n=3 would produce the seq

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

and with n=4:

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

and so on. I solved this using two functions. The first creates the inner seqs and the other pulls them together. Here are my functions:

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

I'm not completely happy with the partition-by-nth function having multiple arity simply for the recursion, but couldn't see another way.

This seems to work just fine with all the test cases. Is this a decent approach? Is it too complicated? Is there a way to do this without recursion or maybe in a single recursive function?

Thanks for the suggestions. I'm new to both Clojure and Lisp, so am picking up the different techniques as I go.

Answer 1

I expect there is a simpler recursive definition which is more in the spirit of The Little Schemer, but the following function using take-nth is quite a bit more compact, since you said you were interested in alternative approaches:

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

which satisfies your examples:

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

In Clojure, the built in libraries will get you surprisingly far; when that fails, use an explicitly recursive solution. This version is also lazy; you'd probably want to use lazy-seq or loop...recur in any "longhand" (explicitly recursive) version to handle large datasets without blowing the stack.