Why does this sorting algorithm do what it should? [Lisp]

Question

I am working on old exams to prepare for my own exam, and the professor is good enough to also give them solutions for them, and now I wonder why one function does what it should.

(defun sortulists (L) (mapcar (lambda (uliste) (sort uliste (lambda (x1 x2) (or (symbolp x2) (and (numberp x1) (numberp x2) (< x1 x2)))))) L)) 

He should take a list L with unsorted sublists that can contain numbers and atoms, and sort its numbers first and put the characters at the end.

When calling the type (sortulists '((A 9 bh 2) (1 mn 9 8) (5 a 7))) it returns ((2 9 HBA) (1 8 9 NM) (5 7 A)) .

Any help?

Edit: fixed indent

Answer 1

The predicate of the sort function indicates which test should be true after sorting the sequence. How sorting is not defined.

If you're struggling with and and or , as they are used here, I suggest you read the Conditional General Lisp chapter : A gentle introduction to symbolic computation . It shows how you can exchange cond , nested if and a combination of and and or , and it provides exercises (and their solutions).

In short, either there must be a character to the right, or, if both are numbers, they must be sorted by size.

Answer 2

 (or ; if x2 is a symbol, then x1 is smaller, whatever x1 is (symbolp x2) ; if both are numbers, then return t if x1 is smaller than x2 (and (numberp x1) (numberp x2) (< x1 x2))) 

So, the numbers are sorted in front. Characters are at the end, but unsorted.

Answer 3

So, to state the obvious:

 (defun sortulists (L) (mapcar (lambda (uliste) (sort uliste (lambda (x1 x2) (or (symbolp x2) (and (numberp x1) (numberp x2) (< x1 x2)))))) L)) 

mapcar simply makes an anonymous function usage list for each element. To just focus on one element '(A 9 bh 2) , you can do:

 ;; same as the anonymous lambda, but named so we can test it a little (defun my< (x1 x2) (or (symbolp x2) (and (numberp x1) (numberp x2) (< x1 x2)))) (sort '(A 9 bh 2) #'my<) ; ==> (2 9 BHA) (my< 2 'a) ; ==> T (my< 2 3) ; ==> T (my< 3 3) ; ==> NIL (my< 'a 2) ; ==> NIL (my< 'a 'b) ; ==> T (my< 'b 'a) ; ==> T 

Looking at my< x1 less than x2 if x2 is a character. x1 also smaller if both are numbers, and x1 is arithmetic less than x2 . For everything else, x1 is equal to or greater than x2 .

If you mix the characters in the argument list a bit, you can see that you get the characters in a different order than the original list. The reason is that the two characters being compared become t in both directions, so 'a less than 'b , and 'b less than 'a . The version in which we keep the character order as a result will look like this:

 (stable-sort '(A 9 bh 2) (lambda (x1 x2) (and (numberp x1) (or (not (numberp x2)) (< x1 x2))))) ; ==> (2 9 ABH) 

Note. I used the stable-sort function because sort not guaranteed to be stable. Stable means that equal objects are stored in the same order as the source.