The Kitchen Sink and Other Oddities

Atabey Kaygun

An Implementation of Pandas’ cut and qcut in Lisp

Description of the problem

There are a lot of useful routines that I like from pandas library. Two of those routines are cut and qcut. Today, I am going to write those functions in common lisp.

There we go!

I am going to implement cut and qcut recursively. One can do this using the loop macro or the do routine, but hey, this is more fun.

(defun cut (xs n)
  "Split a list into n equal-ish pieces."
  (let ((N (ceiling (length xs) n)))
    (labels ((select (ys i zs zss)
               (cond
                 ((null ys) (reverse (cons (reverse zs) zss)))
                 ((zerop i) (select ys N nil (cons (reverse zs) zss)))
                 (t (select (cdr ys) (decf i) (cons (car ys) zs) zss)))))
        (select xs n nil nil))))
CUT

Let us test

(cut (loop repeat 123 collect (random 10)) 9)
((7 1 4 3 5 9 2 6 3 1 7 7 5 1) (6 0 9 1 4 5 3 1 4 7 5 2 7 1)
 (7 2 2 6 9 7 4 4 5 4 8 7 6 0) (6 1 3 7 2 2 0 8 3 2 1 9 0 8)
 (0 7 7 2 5 2 3 4 4 1 4 5 9 4) (5 9 8 1 1 4 7 9 2 1 0 5 3 7)
 (7 3 3 3 7 6 3 1 4 3 3 3 8 0) (7 7 8 2 7 1 3 0 4 8 1 3 0 4)
 (2 1 0 4 0 2 4 7 5 4 5))

And now qcut:

(defun qcut (xs bins)
  (let* ((N (length xs))
     (zs (mapcar #'- (cdr bins) bins))
     (ns (mapcar (lambda (b) (ceiling (* N b))) zs)))
    (labels ((select (ys ms zs zss)
               (cond 
                 ((null ys) (reverse (cons (reverse zs) zss)))
                 ((zerop (car ms)) (select ys (cdr ms) nil (cons (reverse zs) zss)))
                 (t (let ()
                       (decf (car ms))
                       (select (cdr ys) ms (cons (car ys) zs) zss))))))
        (select xs ns nil nil))))
QCUT

with its own test

(qcut (loop repeat 98 collect (random 10)) '(0.0 0.25 0.65 0.85 1.0))
((2 8 2 5 4 4 6 7 2 9 9 6 5 9 7 1 7 6 1 2 9 2 1 1 5)
 (9 1 6 7 1 0 4 5 2 0 1 1 1 1 1 4 4 6 3 1 7 6 2 4 7 5 6 0 9 8 7 8 4 5 5 3 4 6 9
  8)
 (0 8 1 4 0 0 8 4 7 7 8 7 2 9 7 2 5 1 0 6) (0 8 9 4 2 5 0 1 4 1 2 4 7))