To sort out atoms first and then sublists from a list in LISP

Question

I have this homework in LISP where I need to sort out atoms and then sublists from a list. I'm sure this is supposed to be easy task but as I'm not much of a programmer then this is really taking quite a while for me to understand.

I have this list of numbers:

(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6)

And if I understand correctly my task then I should get something like this:

(5 -1 -6 (2 6 1) (8 7 -3) (0 (9 4)))

So far all I found out is how to count atoms and/or sublists but I don't need that.

(DEFUN ATOMNUMBER (L) (COND ((NULL L) 0)
  ((ATOM (CAR L)) (+ 1 (ATOMNUMBER (CDR L))))
  (T (ATOMNUMBER (CDR L))) ))

Also that function should work correctly even when there are only sublists, only atoms or just empty list.

Maybe someone can give me any examples?

Thanks in advance!

Semiaquatic

Answer 1

I am more used to Scheme but here's a solution that works in Lisp:

(defun f (lst)
  (labels 
      ((loop (lst atoms lists)
         (cond
          ((null lst) 
           (append (reverse atoms) (reverse lists)))
          ((atom (car lst))
           (loop (cdr lst) (cons (car lst) atoms) lists))
          (T
           (loop (cdr lst) atoms (cons (car lst) lists))))))
    (loop lst '() '())))

(f '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6))

Basically you iterate over the list, and each element is either appended to the atoms list or the lists lists. In the end you join both to get your result.

EDIT

The remove-if version is way shorter, of course:

(let ((l '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6)))
   (append
    (remove-if-not #'atom l)
    (remove-if     #'atom l)))

Glaser

Could you please give an example what should I edit in first code so it would sort atoms in matrix? For example I have (((4 5) 2)(3 (2) 5)(4 (0) 2 6)) and it should sort atoms like this: ((2 (4 5))(3 5 (2))(4 2 6 (0))) – Semiaquatic

Try (mapcar #'f (((4 5) 2)(3 (2) 5)(4 (0) 2 6))). – Glaser

You're welcome. Just make sure that you actually understand why it works. If not, don't hesitate to ask again. – Glaser

Answer 2

There are several possible approaches in Common Lisp:

• use REMOVE-IF to remove the unwanted items. (Alternatively use REMOVE-IF-NOT to keep the wanted items.) You'll need two lists. Append them.

• use DOLIST and iterate over the list, collect the items into two lists and append them

• write a recursive procedure where you need to keep two result lists.

• it should also be possible to use SORT with a special sort predicate.

Example:

> (sort '(1 (2 6 1) 4 (8 7 -3) 4 1 (0 (9 4)) -6 10 1)
        (lambda (a b)
           (atom a)))

(1 10 -6 1 4 4 1 (2 6 1) (8 7 -3) (0 (9 4)))

As stable version:

(stable-sort '(1 (2 6 1) 4 (8 7 -3) 4 1 (0 (9 4)) -6 10 1)
             (lambda (a b)
               (and (atom a)
                    (not (atom b)))))

(1 4 4 1 -6 10 1 (2 6 1) (8 7 -3) (0 (9 4)))

Garrulity

Thanks, this will help me in my next task (similar to first one). – Semiaquatic

Answer 3

Here's an iterative code, constructing its output in a top-down manner (the comment is in Haskell syntax):

;atomsFirst xs = separate xs id id where
;  separate [] f g  = f (g [])
;  separate (x:xs) f g
;      | atom x = separate xs (f.(x:)) g
;      | True   = separate xs f (g.(x:))

(defmacro app (l v)
   `(progn (rplacd ,l (list ,v)) (setq ,l (cdr ,l))))

(defun atoms-first (xs)
  (let* ((f (list nil)) (g (list nil)) (p f) (q g))
    (dolist (x xs)
      (if (atom x) (app p x) (app q x)))
    (rplacd p (cdr g))
    (cdr f)))

The two intermediate lists that are being constructed in a top-down manner are maintained as open-ended lists (i.e. with explicit ending pointer), essentially following the difference-lists paradigm.

Thump

Answer 4

Just in case you will want to exercise more, and you will find that the examples provided here are not enough :P

(defun sort-atoms-first-recursive (x &optional y)
  (cond
    ((null x) y)
    ((consp (car x))
     (sort-atoms-first-recursive (cdr x) (cons (car x) y)))
    (t (cons (car x) (sort-atoms-first-recursive (cdr x) y)))))

(defun sort-atoms-first-loop (x)
  (do ((a x (cdr a))
       (b) (c) (d) (e))
      (nil)
    (if (consp (car a))
      (if b (setf (cdr b) a b (cdr b)) (setf b a d a))
      (if c (setf (cdr c) a c (cdr c)) (setf c a e a)))
    (when (null (cdr a))
      (cond
        ((null d) (return e))
        ((null c) (return d))
        (t (setf (cdr b) nil (cdr c) d) (return e))))))


(sort-atoms-first-recursive '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6))

(sort-atoms-first-loop '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6))

The second one is destructive (but doesn't create any new conses).

Gambell

Answer 5

You can do this recursive way:

(defun f (lst) 
    (cond 
        ((null lst) nil)
        ((atom (car lst)) 
        (append (list (car lst)) (f (cdr lst)))) 
        (T
            (append (f (cdr lst)) (list (f (car lst))))
        )
    )
)
(step (f '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6)))

Output:

step 1 --> (F '(5 -1 (2 6 1) (8 7 -3) ...))                                                                   
step 1 ==> value: (5 -1 -6 (0 (9 4)) (8 7 -3) (2 6 1))

Ciliata