Re: Collecting like-labelled sublists of a list

On Jul 30, 3:11 am, t...@xxxxxxxxxxxxx (Thomas A. Russ) wrote:
Cortez <relativef...@xxxxxxxxxxxxx> writes:
I need to traverse a list of lists, where each sublist is labelled by
a number, and collect together the contents of all sublists sharing
the same label. So if I have the list -

((0 a b) (1 c d) (2 e f) (3 g h) (1 i j) (2 k l) (4 m n) (2 o p) (4 q
r) (5 s t))

where the first element of each sublist is the label, I need to
produce -

((a b) (c d i j) (e f k l o p) (g h) (m n q r) (s t))

I do this with the following -

(defun test (list)
(loop for j in list
for index = (first j)
for k = (rest j)
with indices = nil
if (not (member index indices))
do (pushnew index indices)
and collect k into res
else
do (nconc (nth index res) k)
finally (return res)))

The one comment that I have about this particular code is that you end
up destructively modifying the original list structure that you start
with. Depending on the precise application that may or may not be a
good idea.

As long as you don't need any of the original structure, you will be
fine. But if the input structure needs to be preserved, you are in
trouble.

To see the effect, try the following:

(defvar *input* (copy-tree '((0 a b)
(1 c d)
(2 e f)
(3 g h)
(1 i j)
(2 k l)
(4 m n)
(2 o p)
(4 q r)
(5 s t))))

;; I use copy-tree to avoid problems with destructively modifying
;; constant list structure.

(test *input*)
=> ((A B) (C D I J) (E F K L O P) (G H) (M N Q R) (S T))

*input*
=> ((0 A B) (1 C D I J) (2 E F K L O P) (3 G H) (1 I J)
(2 K L O P) (4 M N Q R) (2 O P) (4 Q R) (5 S T))

Note in particular the changes to the first occurences of the lists
headed by 1, 2 and 4.

--
Thomas A. Russ, USC/Information Sciences Institute

Yes, thanks for pointing that out - I should have mentioned that the
destructive modification is not, in fact, an issue.
.

Relevant Pages

  • Re: Are the lists produced by backquote always non-literal?
    ... >> structure with the template itself. ... a pity, it seems, that backquote isn't just defined to always generate ... building up lists. ... new list structure and when it won't so it can't be used this way--it ...
    (comp.lang.lisp)
  • Re: a noob question
    ... In the syntax for LET, since you have zero or more bindings, and zero ... the list structure has to be such that you know which constituents are ... why are the binding forms themselves lists? ...
    (comp.lang.lisp)
  • Re: Collecting like-labelled sublists of a list
    ... and collect together the contents of all sublists sharing ... the same label. ... up destructively modifying the original list structure that you start ... Note in particular the changes to the first occurences of the lists ...
    (comp.lang.lisp)
  • Re: flatten
    ... easy to just hose a CPU if I do not know about list structure". ... How fast is the fastest Lisp solution for flatten of list of n ... lists with n elements that "Lisp expert" can manage? ... Actually, it is not _only_ about consing, but generally about ...
    (comp.lang.lisp)