Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Process n items from a list at a time in Lisp

Tags:

common-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?

like image 755
Sunder Avatar asked Jun 19 '13 18:06

Sunder


People also ask

How do I iterate over a list in LISP?

To iterate over a list, 2 items at a time we use a combination of on , by and destructuring. We use on to loop over the rest (the cdr ) of the list.

What does list do in LISP?

The list function is rather used for creating lists in LISP. The list function can take any number of arguments and as it is a function, it evaluates its arguments. The first and rest functions give the first element and the rest part of a list.

Is everything a list in LISP?

Lisp has one: everything is a list. The first element is a function name, and the rest are its arguments. Thus, the language is simply a collection of compile- and run-time functions, trivially extensible.


2 Answers

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))
like image 142
Joshua Taylor Avatar answered Oct 22 '22 22:10

Joshua Taylor


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

like image 23
DJG Avatar answered Oct 23 '22 00:10

DJG