LAMBDA expressions used as comparison operators for sorting

A reader of my book on AutoLISP/Visual LISP asked for an explanation on this subject.

As I believe it could be of general interest I would like to share my answer.

This is the answer I published as a comment in my blog lispexpert.blogspot.com:

A reader asked me a couple of days ago:

I’m completely stumped by the last function on Page 74:

(defun sort-list (lst func)

(mapcar '(lambda (x) (nth x lst))

(vl-sort-i lst func)))

;;;Listing 5.8. List sorting function.

What I DON’T understand, is how

'(lambda (a b) (

is used as the “func” argument in sort-list, and how it is applied to the underlying (vl-sort-i lst func) part of the defun.

Your question sums up to one issue: How do the Visual LISP sorting functions work?

Vl-sort and vl-sort-i operate as what is known as a Comparison Sort. This means that it reads two list elements comparing them through the comparison operator supplied to find which of the two elements should occur first in the final sorted list. There are many algorithms that may be used to do this, the one used internally is not documented. For more information on the subject of Comparison Sorting algorithms you can see http://en.wikipedia.org/wiki/Comparison_sort.

But let’s see how vl-sort and vl-sort-i work. As they use a Comparison Sort algorithm they operate taking a pair of values and applying to them the comparison operator. This means that they operate repeatedly by comparing two of the list’s terms each time and performing some kind of reordering that depends on the sorting algorithm implemented.

You said that:

“What I DON’T understand, is how ‘(lambda (a b) (

The reason this can be done is precisely that vl-sort and vl-sort-i take each time a pair of arguments from the list. These arguments are the ones that the lambda function identifies with the symbols a and b.

Let’s assign a list of points to a symbol, let’s say lst. As we are only going to compare the first term of each sublist, the other values are of no interest, so we will use just zeros. Could be any number:

(setq lst '((9 0 0)(2 0 0)(6 0 0)(4 0 0)(7 0 0)))

To check which numbers are compared each time by the sorting functions we will modify the the lambda expression so it will also print to the console the values received as a and b. This will be done by nesting the first car in a print expression and the second car in a princ expression. This way print will introduce a new-line before a’s value and a space after it. Then princ will output b’s value printed in the same line. This way the values compared in each cycle will be printed on a different line.

_$ (vl-sort lst '(lambda (a b) ( print (car a))(princ (car b)))))

2 9

7 4

4 6

7 6

4 2

4 9

6 9

7 9((2 0 0) (4 0 0) (6 0 0) (7 0 0) (9 0 0))

As we can see, vl-sort checks the following relations to sort the list:

If 2 is less than 9,

If 7 is less than 4,

If 4 is less than 6,

If 7 is less than 6,

If 4 is less than 2,

If 4 is less than 9,

If 6 is less than 9,

If 7 is less than 9.

After the last pair of numbers vl-sort returns the sorted list, in this case the sorted point list.

If we do the same using vl-sort-i the only difference is that the list returned will not include the point sublists, but their indices. This is why this returned list is processed to recover, using the nth function, the sublists identified by these indices. Then why use vl-sort-i? It is documented that in certain cases vl-sort will delete repeated entries. So this way we can guarantee that no item will be lost in the sorting.

Vl-sort and vl-sort-i are welcome additions to AutoLISP. Before Visual LISP we would have to program our own sorting functions. As Reini Urban stated “Generally speaking, sorting in plain AutoLISP is a pain in the ass”. http://autocad.xarch.at/lisp/#sort

Mr.Togores,

I know that this thread is fairly old, but I wanted to thank you about creating it and sharing this information.

As for myself - whos starting learning how to deal with vl-sort / vl-sort-i functions I thought why there isn't a function that

(vl-sort) Returns A list containing the elements of lst in the order specified by comparison-function.

but also

(vl-sort-i) Duplicate elements will be retained in the result.

where your (sort-list) example function just does that:

_$ 
(defun sort-list (lst func)
(mapcar (function (lambda (x) (nth x lst)))
	(vl-sort-i lst func)
)
)
SORT-LIST

(setq StrLst '("A" "C" "B" "E" "A" "D" "B" "A" "C"))
("A" "C" "B" "E" "A" "D" "B" "A" "C")

_$ (vl-sort-i StrLst (function (lambda (a b) (< a b))))
(7 4 0 6 2 8 1 5 3)
_$ (vl-sort StrLst (function (lambda (a b) (< a b))))
("A" "A" "A" "B" "B" "C" "C" "D" "E")
_$ (sort-list StrLst (function (lambda (a b) (< a b))))
("A" "A" "A" "B" "B" "C" "C" "D" "E")

_$ (setq IntLst '(10 30 20 40 10 50 20 10 30))
(10 30 20 40 10 50 20 10 30)

_$ (vl-sort-i IntLst (function (lambda (a b) (< a b))))
(7 4 0 6 2 8 1 3 5)
_$ (vl-sort IntLst (function (lambda (a b) (< a b))))
(10 20 30 40 50)
_$ (sort-list IntLst (function (lambda (a b) (< a b))))
(10 10 10 20 20 30 30 40 50)

I thought about writing such function (I didn't figure the (lambda (x) (nth x lst)) part), but now I've found that such exists.

Another wonderful example is showing how to use function as an argument in a subfunction.

I don't know if you are still active in this forum, but I was surprised that this thread haven't got any replies, about this. So I'm reviving it, as it would be helpful for the learning users, like me.

FWIW, note that the lambda function is not required in your examples as only a single function is being evaluated with the two arguments:

_$ (vl-sort '(6 2 7 4 8 9) '<)
(2 4 6 7 8 9)

Where sorting in AutoLISP is concerned, here are a few caveats to be aware of:

Removal of duplicate integers when using vl-sort:

_$ (vl-sort '(6 2 7 2 2 4 1 1 8 9) '<)
(1 2 4 6 7 8 9)

Strings are sorted by character using the ASCII character code, which may lead to unexpected results:

_$ (vl-sort '("1" "4" "11" "2" "6" "101") '<)
("1" "101" "11" "2" "4" "6")

Thanks Lee,

I'm trying to get used with lambda (as I find it very useful for dealing with assoc lists):

(setq Lst
(list
	(list 1 "D" "B" "E" "A")
	(list 2 "B" "C" "A" "C")
	(list 3 "C" "A" "B" "E")
	(list 4 "E" "C" "F" "A")
	(list 5 "A" "E" "D" "B")
)
)

(defun SortAssocLstByNth ( Lst Num / )
(mapcar 
	(function (lambda (x) (nth x Lst)))
	(vl-sort-i 
		Lst 
		(function (lambda (a b) (< (nth Num a) (nth Num b))))
	)
)
)


_1$ (foreach x (SortAssocLstByNth Lst 3) (print x))
(2 "B" "C" "A" "C") 
(3 "C" "A" "B" "E") 
(5 "A" "E" "D" "B") 
(1 "D" "B" "E" "A") 
(4 "E" "C" "F" "A")
_1$ 


_1$ (foreach x (SortAssocLstByNth Lst 3) (print x))
(2 "B" "C" "A" "C") 
(3 "C" "A" "B" "E") 
(5 "A" "E" "D" "B") 
(1 "D" "B" "E" "A") 
(4 "E" "C" "F" "A")
_1$ 

I was aware of your second example, but I was attempting something like this:

; retaining duplicate integers (with vl-sort-like result) using (vl-sort-i):
_1$ (setq Lst '(6 2 7 2 2 4 1 1 8 9))
(6 2 7 2 2 4 1 1 8 9)
_1$ (mapcar '(lambda (x) (nth x Lst)) (vl-sort-i Lst '<))
(1 1 2 2 2 4 6 7 8 9)

I appreciate your last example, as I didn't knew nor notice how the string-numbers might be sorted (obviously you knew this from experience).

Its amazing how many details you know - you are like talking AutoCAD.