A reader of my book on AutoLISP/Visual LISP (
https://www.createspace.com/3973821) 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
http://lispexpert.blogspot.com/p/chapter-3-visual-lisp-ide.html#ch5:
A reader asked me a couple of days ago:
I’m completely stumped by the last function on Page 74:
;;;Listing 5.8. List sorting function.
What I DON’T understand, is how
'(lambda (a b) ( < (car a) (car 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) ( < (car a) (car 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.”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.
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