Visual LISP, AutoLISP and General Customization

Visual LISP, AutoLISP and General Customization

Reply
Valued Contributor
Rtogores
Posts: 84
Registered: ‎02-07-2001
Message 1 of 2 (356 Views)

LAMBDA expressions used as comparison operators for sorting

356 Views, 1 Replies
02-03-2013 10:14 AM

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:

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

 

_$ (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 ****”. http://autocad.xarch.at/lisp/#sort

*Expert Elite*
hmsilva
Posts: 3,343
Registered: ‎12-17-2004
Message 2 of 2 (354 Views)

Re: LAMBDA expressions used as comparison operators for sorting

02-03-2013 10:43 AM in reply to: Rtogores

Reinaldo,

many thanks for sharing.

 

Cheers

Henrique

Post to the Community

Have questions about Autodesk products? Ask the community.

New Post
Announcements
Do you have 60 seconds to spare? The Autodesk Community Team is revamping our site ranking system and we want your feedback! Please click here to launch the 5 question survey. As always your input is greatly appreciated.