Why does replacing "(null x)" with "(null (cdr x))" make this code work?

Question

I'm a newbie in LISP. I'm trying to write a bubble sort function in LISP.

This is what I've done so far.

(defun mysort (x)
  (if (null  x) x
    (if (< (car x) (cadr x))
     (cons (car x) (mysort (cdr l)))
     (cons (cadr x) (mysort (cons (car x) (cddr x)))))))

I'm getting an error

NIL is not a real number

When I modified the code like (after referring several codes)-

(defun mysort (x)
  (if (null  (cdr x)) x
   (if (< (car x) (cadr x))
    (cons (car x) (mysort (cdr l)))
    (cons (cadr x) (mysort (cons (car x) (cddr x)))))))

Now it works fine.

Why does replacing (if (null x) x...) with (if (null (cdr x)) x...) make a difference?

Also, I'm calling mysort from another function to run it (length x) number of times. Is it possible to achieve complete sorting in a single recursive loop, only using the basic functions?

Answer 1

To do a comparison you need at least two elements so checking if x is NIL is not enough.

Checking if (cdr x) is NIL is a nice way to check that the list length is at least two because NIL is special and even if it's not a cons cell it's guaranteed that (cdr NIL) is NIL.

The error you were getting is because NIL is not a number thus you cannot compare with < a number with it and this was happening when executing (< (car x) (cadr x)) when x was a list with a single element.

About sorting in a single recursive call you could use this definition of sorting:

• an empty list is sorted
• a non-empty list is sorted if the first element is the minimum of the list and the rest of the list is sorted.

This leads to

(defun mysort (x)
  (if x
      (let ((minimum (reduce #'min x)))
        (cons minimum
              (mysort (remove minimum x :count 1))))))

That, by the way, is a very inefficient way to do the sorting.

Answer 2

If you want to see if the first element is smaller than the second element, then the list needs to have at least two elements.

If there is only one element, CADR returns NIL. This is not a number.

CL-USER 18 > (cadr '(1))
NIL

Your Lisp system should not only tell you the error, but also the function where it occurred. Here: the function <.

Using (null (cdr list)) is a good way to test if there is a second element. A typical error would be to call LENGTH, which is inefficient.