CODEWITHSUNDEEP
common-lisp
Sunder
Sunder

Reputation: 1513

Process n items from a list at a time in Lisp

Given a list, how do I process N items at a time? Ruby has each_slice method on the Enumerable that does this; what would be the Lisp equivalent?

Upvotes: 7

Views: 1557

Answers (4)

Everton J. Carpes
Everton J. Carpes

Reputation: 362

All the answers are practical and can be used, but I believe none replicates exactly the Ruby's behavior:

> 1.upto(7).each_slice(3) { |x, y, z| p [x, y, z] }
[1, 2, 3]
[4, 5, 6]
[7, nil, nil]

To emulate Ruby, I believe the proper code is something similar to:

CL-USER> (defun each-slice (n list thunk)
  (apply thunk (loop for i below n collect (nth i list)))

  (if (> (length list) n)
      (each-slice n (subseq list n) thunk)))

Generates a similar response when called:

CL-USER> (each-slice 3 '(1 2 3 4 5 6 7) (lambda (x y z) (print (list x y z))))

(1 2 3) 
(4 5 6) 
(7 NIL NIL) 
NIL

Upvotes: 0

Joshua Taylor
Joshua Taylor

Reputation: 85913

Common Lisp's loop can be used for this very nicely, as in the following two examples. The first example loops for (x y z) in a list. However, the default step is cdr (rest), so if the list is (1 2 3 4 5), you get (1 2 3), (2 3 4), etc., for (x y z).

CL-USER> (loop for (x y z) on '(1 2 3 4 5 6 7 8 9 10 11 12)
              do (print (list z y x)))

(3 2 1) 
(4 3 2) 
(5 4 3) 
(6 5 4) 
(7 6 5) 
(8 7 6) 
(9 8 7) 
(10 9 8) 
(11 10 9) 
(12 11 10) 
(NIL 12 11) 
(NIL NIL 12) 
NIL

If you do not want the overlap between iterations, specify the stepping function to be something that moves farther down the list. For instance, if you're pulling three elements at a time, use cdddr:

CL-USER> (loop for (x y z) on '(1 2 3 4 5 6 7 8 9 10 11 12) by 'cdddr
              do (print (list z y x)))
(3 2 1) 
(6 5 4) 
(9 8 7) 
(12 11 10) 
NIL

Implementing partition with this technique

Another answer implemented the counterpart to each_slice using an auxiliary function. However, notice that partition (in that sense) is just each_slice with the identity function. This suggests that we should be able to implement it using the idiom above. The anonymous function 

(lambda (list)
  (nthcdr n list))

is the step function that we need. Since we do not know how many elements the cells have until run time, we can't bind each element like we did above with (x y z). We do have to match each tail of the list as we step down and extract the subsequence n elements. Here's a loop based implementation of partition.

CL-USER> (defun partition (list cell-size)
           (loop for cell on list by #'(lambda (list)
                                         (nthcdr cell-size list))
              collecting (subseq cell 0 cell-size)))
PARTITION

CL-USER> (partition '(1 2 3 4 5 6) 2)
((1 2) (3 4) (5 6))

Upvotes: 8

sds
sds

Reputation: 60064

If you wanted to split your list on a predicate (as opposed to a fixed length sublists), I would have recommended nsplit-list.

For fixed length sublists, you may want to use loop: 

(defun by-N (list n fun) 
  (loop for tail on list by (lambda (l) (nthcdr n l)) 
    do (funcall fun (subseq tail 0 (min (length tail) n)))))
(by-n (loop for i from 0 to 20 collect i) 5 #'print)

(0 1 2 3 4) 
(5 6 7 8 9) 
(10 11 12 13 14) 
(15 16 17 18 19) 
(20)

Note that this is not very efficient (it scans the list more than necessary and allocates a fresh sublist for passing to fun).

The efficient version is more complicated:

(defun batch-map (list batch-size function)
  "Call FUNCTION on sublists of LIST of size BATCH-SIZE.
Returns the list of return values of FUNCTION."
  (do ((tail list (cdr end)) end ret (bs1 (1- batch-size)))
      ((endp tail) (nreverse ret))
    (setq end (nthcdr bs1 tail))
    (if (consp end)
        (let ((next (cdr end)))
          (setf (cdr end) nil)
          (unwind-protect (push (funcall function tail) ret)
            (setf (cdr end) next)))
        (push (funcall function tail) ret))))

Upvotes: 3

DJG
DJG

Reputation: 6563

(defun partition-helper (lst acc x)
  (if (< (length lst) x)
    acc
    (partition-helper (subseq lst x) (cons (subseq lst 0 x) acc) x)))

(defun partition (lst x)
  (reverse (partition-helper lst '() x)))

Then you can:

[25]> (PARTITION '(1 2 3 4 5 6) 2)
((1 2) (3 4) (5 6))

or:

[26]> (PARTITION '(1 2 3 4 5 6) 3)
((1 2 3) (4 5 6))

and then just mapcar over the list to process it 2 or 3 elements at a time.

Upvotes: 3

Related Questions