Your code works but has some efficieny problems, as already pointed out by Rainer Joswig ("it conses like mad"). Now that you posted a modified version I added some details at the end of the answer.
I like Joshua Taylor's answer because it is both efficient and simple.
However, I'd like to take another approach and define
split-n efficiently (by, e.g. avoiding whenever possible needless memory allocation) while providing more control to the programmer over the function's behavior (like standard functions and macros in Common Lisp generally do; e.g.
:from-end arguments, etc.).
All the following code can be found here.
This was unexpected:
the last subsequence getting the remaining elements
I agree that this behavior might be desirable, but I think the expected property of the split function would be to return sequences having no more than
n elements. We can see that this is the behavior of
serapeum:batches, which is another interesting implementation to read.
I'd rather have
split-n let me choose what to do with the remaining parts. That's why I add a
:last argument which may take the following values:
:undersized: have a last group with fewer elements
:oversized: join the remaining elements with the preceding group (what you want)
:truncated: discard the remaining elements and return them as another value
The default value when no argument is given, or when
NIL are given, would be what I consider the least suprising option, namely
:undersized. I think
:truncate should be asked for explicitely because it changes the expected return values.
Moreover, the function can be used in more circumstances if we have a way to allow (resp. disallow) the resulting parts from sharing data with the original sequence. This can be controlled by a boolean
:sharedp argument (see e.g.
For example, splitting an array into sub-arrays of
n elements could possibly return displaced arrays: any modification to the original element would be visible in the corresponding sub-array, and inversely.
Likewise, it may be desirable that an original list and the splitted lists share a common tail: imagine a queue where a producer adds elements to the end of the queue, and a consumer function extracts elements by batches of
n elements; the following call:
(split-n queue n :last :truncated :sharedp t)
... would grab a lists of sequences of size
n, and the remaining elements returned as a second value would be the new head of the queue, the tail being left untouched.
Finally, we may want to control the type of the output sequence, as suggested in comments. For now, the accepted result type is either
vector. We could also pass a function designator so that we can feed directly a consumer with the subsequences instead of collecting them first (see
do-batches in the pasted code).
split-n returns 2 values:
a list of non-empty subsequences of sequence
:undersized, the only subsequence that may not have exactly
n elements is the last subsequence; if so, it contains 1 or more elements but less than
:oversized, all subsequences but the last have exactly
n elements; the last subsequence can contain fewer or more than
n elements (fewer if
n is larger than the size of the original sequence; more if the size is larger but not exactly divisible by
:truncated, all returned subsequences have exactly
A generalized boolean which indicates whether there were remaining elements:
In a previous version, I used
serapeum:collecting but since we are interested in having different possible return types (list or vectors), I wrote little helper functions to collect elements.
(defparameter *pouch* nil)
(defun queue-collector ()
(let ((q (serapeum:queue)))
(lambda (x) (serapeum:enq x q))
(lambda () (serapeum:qlist q)))))
(defun vector-collector (size)
(let ((v (make-array size :fill-pointer 0 :adjustable nil)))
(lambda (x) (vector-push x v))
(lambda () v))))
(defun take (value &optional (cons *pouch*))
(funcall (car cons) value))
(defun loot (&optional (cons *pouch*))
(funcall (cdr cons)))
(defun call-while-hoarding (function &key (result-type 'list) size)
(let ((*pouch* (ecase result-type
(vector (if size
(defmacro hoarding ((&rest args) &body body)
;; parse: name is optional
(let* ((name-p (not (keywordp (first args))))
(args (if name-p (cdr args) args))
(name (when name-p (car args))))
`((let ((,name *pouch*)) ,@body))
hoarding macro binds a new collector in the special variable
*pouch*, which is a
cons of two closures: one to collect elements, the other to retrieve all collected elements. Those closures are respectively called by helper functions,
serapeum:collecting, collectors can be named and specialized on the return type. Unfortunately, the
return-type option is not as smart as the one for
map which accepts type specifier with element types and sizes. Here, the expected size can be specified too, but no check is done to ensure that
(loot) returns a collection of the expected size (we can call
(loot) multiple times, after all).
(defun split-n (sequence n
&key last sharedp (result-type 'list)
&aux (size (length sequence)))
(check-type sequence sequence)
(check-type n (integer 1 *))
;; let the value be checked by "hoarding"
;; (check-type result-type (member list vector))
((nil t) (setf last :undersized))
((:truncated :oversized :undersized) last))
(let* ((type (array-element-type sequence))
(copy (if sharedp
(lambda (b e)
(make-array (- e b)
(lambda (b e)
(subseq sequence b e)))))
(lambda (&optional tail)
(when (< beg size)
(funcall copy beg size))
(prog1 (funcall copy beg end)
(setf beg end
end (+ n end)))))))
(if sharedp #'identity #'copy-list))
(lambda (&optional tail)
(funcall copy current)
(prog1 (subseq current 0 n)
(setf current (nthcdr n current)))))))))))
(multiple-value-bind (count remainder) (truncate size n)
(hoarding (:result-type result-type
:size (ecase last
(:undersized (+ count (signum remainder)))
(dotimes (_ (ecase last
(:oversized (1- count))
(take (funcall slice)))
(let ((residual (funcall slice t)))
(when residual (take residual))
((zerop remainder) nil)
((eq last :undersized) remainder)
(t (min size (+ remainder n))))))
(:truncated (values (loot)
Edit: I ran exhaustive tests and fixed a lot of corner cases. Also, you can see that I factorized lists and arrays in a single method. Test results have been updated.
Firt, enable tracing:
Then, we run it for some combinations of inputs:
#P"/tmp/pastebin" :direction :output :if-exists :supersede)
(dolist (last '(:undersized :oversized :truncated))
(dolist (shared '(nil t))
(dolist (type '(vector list))
(dolist (input (list #() '()
'(a b c) #(a b c)
'(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
#(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
"something in a string"))
(dolist (n '(1 2 3 4 5 6 7 8))
(split-n input n :last last :sharedp shared :result-type type)
Results are available on pastebin.
(edit) Back to your code
I go back to your original question as well as your answer. Even though the code is readable and well organized, you are doing some nasty things maybe without realizing it:
SUBSEQ always create a copy of the input sequence. You create copies for the head and the tail in
partition, for example. Imagine a sequence of thousand elements splitted by groups of 10: it might be inevitable to allocate 100 subsequences, but this is not what happens because you needlessly copy many more sequences at each step:
- partition into a head, a sequence of 10 elements, and a tail, a sequence of 990 elements.
- parition that copy into a head, and the next tail, a sequence of 980 elements.
- .... repeat the process: how many times are elements being copied? Half a million times? You accidentally wrote code with quadratic complexity impacting both time and memory.
:oversized case, you still
append lists; here, you could use
nconc instead of
append. Since you just created the list and nobody else has a reference to it, why not mutate it?
In the same place, you write:
(apply #'(lambda (x y) (concatenate result-type x y)) oversized)
IMHO the lambda is not really useful and the thing could be written:
(concatenate result-type (first oversized) (second oversized))
But still, you took a sequence, split it in parts, then extract the last two elements and join them, which is quite some work. This is not catastrophic eiter, but since
truncate can give you the size in advance you can avoid doing unnecessary work.
By the way, you remove 2 from
n in order to get the last two subsequences: did you check what happens when splitting
"abcd" by 10 using the
Your code is readable and the major efficiency hit comes from repeatedly calling
subseq. I'd suggest trying to write the most over-engineered, gold-plated solution you can do, just as an exercise. This will force you to consider all possible corner cases and see if you can refactor things a little more. Good luck!