Partition a sequence

Description of the problem

Given a sequence \((a_n)\) and a predicate \(f(x,y)\), we want to split the sequence into subsequences \((a_{n+i})_{i=0}^k\) with the property that \(f(a_j,a_{j+1})\equiv T\) for every \(n\leq j\leq n+i-1\).

A tail recursive functional implementation

The following is a tail recursive implementation of a solution of the problem I posed above:

(defun partition-by (seq fn &optional acc tem)
   (cond ((null seq) (reverse (cons (reverse tem) acc)))
         ((null tem) (partition-by (cdr seq) fn acc (list (car seq))))
         ((funcall fn (car tem) (car seq)) (partition-by (cdr seq) fn acc (cons (car seq) tem)))
         (t (partition-by (cdr seq) fn (cons (reverse tem) acc) (list (car seq))))))
PARTITION-BY

And here is a test in which we group integers according to their parity (even-ness/odd-ness)

(defvar test-list '(0 2 4 1 3 0 2 4 6 1 3 5 7 9 0 2 4 6 8 1))
TEST-LIST

(partition-by test-list (lambda (x y) (equal (evenp x) (evenp y))))
((0 2 4) (1 3) (0 2 4 6) (1 3 5 7 9) (0 2 4 6 8) (1))

We can use this function to group the terms in fixed sizes. For that the function we pass must be stateful

(defun delim (m)
   (let ((n 0))
      (lambda (x y)
          (setf n (mod (1+ n) m))
          (> n 0))))
DELIM

(partition-by test-list (delim 3))
((0 2 4) (1 3 0) (2 4 6) (1 3 5) (7 9 0) (2 4 6) (8 1))

(partition-by test-list (delim 7))
((0 2 4 1 3 0 2) (4 6 1 3 5 7 9) (0 2 4 6 8 1))

Or, we can partition the sequence into increasing subsequences

(partition-by test-list (lambda (x y) (<= x y)))
((0 2 4) (1 3) (0 2 4 6) (1 3 5 7 9) (0 2 4 6 8) (1))

An imperative implementation

The recursive implementation might blow up the stack if your lisp does not employ tail recursion elimination and if the sequence passed to it is large. In order to avoid this problem, one must implement it imperatively.

(defun partition-by (seq fn)
  (let* ((acc nil)
         (y (car seq))
         (tem (list y)))
    (dolist (x (cdr seq) (reverse (cons (reverse tem) acc)))
       (if (funcall fn y x)
          (push x tem)
          (progn (push (reverse tem) acc)
                 (setf tem (list x))))
       (setf y x))))
PARTITION-BY

Let me test it on the examples I gave above:

(partition-by test-list (lambda (x y) (equal (evenp x) (evenp y))))
((0 2 4) (1 3) (0 2 4 6) (1 3 5 7 9) (0 2 4 6 8) (1))

(partition-by test-list (delim 3))
((0 2 4) (1 3 0) (2 4 6) (1 3 5) (7 9 0) (2 4 6) (8 1))

(partition-by test-list (lambda (x y) (<= x y)))
((0 2 4) (1 3) (0 2 4 6) (1 3 5 7 9) (0 2 4 6 8) (1))