3

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!

5 Answers 5

6

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)))
1
  • Thanks, this will help me in my next task (similar to first one). May 14, 2012 at 9:19
2

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)))
3
  • 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))) May 15, 2012 at 18:42
  • 1
    Try (mapcar #'f (((4 5) 2)(3 (2) 5)(4 (0) 2 6))).
    – uselpa
    May 15, 2012 at 18:47
  • You're welcome. Just make sure that you actually understand why it works. If not, don't hesitate to ask again.
    – uselpa
    May 15, 2012 at 18:56
0

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

0

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.

0

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))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.