An idiomatic way to group a sorted list of integers?

Question

I have a sorted list of integers, (1 2 4 5 6 6 7 8 10 10 10) . I want to group them all to get ((1) (2) (4) (5) (6 6) (7) (8) (10 10 10)) .

So far, I have this that works:

 (let ((current-group (list)) (groups (list))) (dolist (n *sorted*) (when (and (not (null current-group)) (not (eql (first current-group) n))) (push current-group groups) (setf current-group (list))) (push n current-group)) (push current-group groups) (nreverse groups)) 

But I'm sure there must be a lot more LISPy for this. Any ideas?

Answer 1

Not so bad. I would write it like this:

 (defun group (list) (flet ((take-same (item) (loop while (and list (eql (first list) item)) collect (pop list)))) (loop while list collect (take-same (first list))))) CL-USER 1 > (group '(1 2 4 5 6 6 7 8 10 10 10)) ((1) (2) (4) (5) (6 6) (7) (8) (10 10 10)) 

Answer 2

There is already an accepted answer , but I think it's worth looking at a different way of decomposing this problem, although the approach here is essentially the same). Firstly, let it determine the section that takes the list and the predicate, and return the list prefix and suffix, where the suffix starts with the first element of the list that satisfies the predicate, and the prefix is ​​all to the point that there wasn’t

 (defun cut (list predicate) "Returns two values: the prefix of the list containing elements that do no satisfy predicate, and the suffix beginning with an element that satisfies predicate." (do ((tail list (rest tail)) (prefix '() (list* (first tail) prefix))) ((or (funcall predicate (first tail)) (endp tail)) (values (nreverse prefix) tail)))) 

 (cut '(1 1 1 2 2 3 3 4 5) 'evenp) ;=> (1 1 1) (2 2 3 3 4 5) (let ((l '(1 1 2 3 4 4 3))) (cut l (lambda (x) (not (eql x (first l)))))) ;=> (1 1), (2 3 4 4 3) 

Then, using cut, we can navigate through the input list using prefixes and suffixes with a predicate that checks if the non-eql element is not the first element of the list. That is, starting from (1 1 1 2 3 3), you would cut the predicate check into "not eql to 1" to get (1 1 1) and (2 3 3). You would add the first to the list of groups, and the second would become the new tail.

 (defun group (list) (do ((group '()) ; group initial value doesn't get used (results '() (list* group results))) ; empty, but add a group at each iteration ((endp list) (nreverse results)) ; return (reversed) results when list is gone (multiple-value-setq (group list) ; update group and list with the prefix (cut list ; and suffix from cutting list on the (lambda (x) ; predicate "not eql to (first list)". (not (eql x (first list)))))))) 

 (group '(1 1 2 3 3 3)) ;=> ((1 1) (2) (3 3 3)) 

When implementing cut

I tried to make this slice relatively efficient as it skips only one list. Since member returns the entire tail of a list that starts with the element found, you can actually use member with :test-not to get the desired tail:

 (let ((list '(1 1 1 2 2 3))) (member (first list) list :test-not 'eql)) ;=> (2 2 3) 

Then you can use ldiff to return the prefix that precedes this tail:

 (let* ((list '(1 1 1 2 2 3)) (tail (member (first list) list :test-not 'eql))) (ldiff list tail)) ;=> (1 1 1) 

This is a simple question to combine approaches and return tail and prefix as multiple values. This gives a cut version that takes only a list as an argument and may be easier to understand (but it is a little less efficient).

 (defun cut (list) (let ((tail (member (first list) list :test-not 'eql))) (values (ldiff list tail) tail))) (cut '(1 1 2 2 2 3 3 3)) ;=> (1 1), (2 2 2 3 3) 

Answer 3

I like to use reduce :

 (defun group (lst) (nreverse (reduce (lambda (re) (if (and (not (null r)) (eql e (caar r))) (cons (cons e (car r)) (cdr r)) (cons (list e) r))) lst :initial-value nil))) 

or using push :

 (defun group (lst) (nreverse (reduce (lambda (re) (cond ((and (not (null r)) (eql e (caar r))) (push e (car r)) r) (t (push (list e) r)))) lst :initial-value nil)))