Sorting a list made out of manual structures in lisp

Question

I have a structure in my code

(defstruct tree-node char freq )

And i have a list of these 'nodes'. For example (#\a 4, #b 5, #q 17) and i want to sort them in descending order. How can i use the sort function. I have written a comparison function but i don't know if this a way to do it.

(defun compare()( if( > (tree-node-freq tree-node-freq) T (nil))))

When i call the sort function

(sort list compare)

it says that compare function has no value. By the way i am new to lisp so don't judge please :)

Answer 1

The sort function expects a predicate function that takes two arguments and returns a generalized boolean, while the OP code shows a comparison function that takes no arguments. There is no reason to use if when the comparison itself returns the desired boolean. Also note that the sharp-quote is required to access the function in the sort expression, i.e., (sort list #'compare) instead of (sort list compare).

You could write the comparison function as:

CL-USER> (defun node-greater-p (n1 n2)
           (> (tree-node-freq n1) (tree-node-freq n2)))
NODE-GREATER-P

CL-USER> *nodes*
(#S(TREE-NODE :CHAR #\a :FREQ 4) #S(TREE-NODE :CHAR #\b :FREQ 5)
 #S(TREE-NODE :CHAR #\q :FREQ 17))

CL-USER> (sort *nodes* #'node-greater-p)
(#S(TREE-NODE :CHAR #\q :FREQ 17) #S(TREE-NODE :CHAR #\b :FREQ 5)
 #S(TREE-NODE :CHAR #\a :FREQ 4))

You could just as well do this with an anonymous function:

CL-USER> *nodes*
(#S(TREE-NODE :CHAR #\a :FREQ 4) #S(TREE-NODE :CHAR #\b :FREQ 5)
 #S(TREE-NODE :CHAR #\q :FREQ 17))

CL-USER> (sort *nodes* #'(lambda (n1 n2) (> (tree-node-freq n1) (tree-node-freq n2))))

(#S(TREE-NODE :CHAR #\q :FREQ 17) #S(TREE-NODE :CHAR #\b :FREQ 5)
 #S(TREE-NODE :CHAR #\a :FREQ 4))

But, it would be even better to take advantage of the :key argument of the sort function which provides a sort key:

CL-USER> *nodes*
(#S(TREE-NODE :CHAR #\a :FREQ 4) #S(TREE-NODE :CHAR #\b :FREQ 5)
 #S(TREE-NODE :CHAR #\q :FREQ 17))

CL-USER> (sort *nodes* #'> :key #'tree-node-freq)

(#S(TREE-NODE :CHAR #\q :FREQ 17) #S(TREE-NODE :CHAR #\b :FREQ 5)
 #S(TREE-NODE :CHAR #\a :FREQ 4))

Answer 2

If you define your compare function in the REPL, we see warnings:

(defun compare()( if( > (tree-node-freq tree-node-freq) 
                               T
                               nil)))
; in: DEFUN COMPARE
;     (IF (> (SBCLI::TREE-NODE-FREQ SBCLI::TREE-NODE-FREQ) T NIL))
; 
; caught ERROR:
;   error while parsing arguments to special operator IF:
;     too few elements in
;       ((> (TREE-NODE-FREQ TREE-NODE-FREQ) T NIL))
;     to satisfy lambda list
;       (SB-C::TEST SB-C::THEN &OPTIONAL SB-C::ELSE):
;     between 2 and 3 expected, but got 1
; 
; compilation unit finished
;   caught 1 ERROR condition
COMPARE

You put the closing parenthesis of > too far away. Instead of > a b we only got > (a) b c. So the if doesn't have a then nor an else clause.

You might want to use an editor with lisp indentation.

Compare

Looking at sort's documentation:

SORT names a compiled function:
  Lambda-list: (SEQUENCE SB-IMPL::PREDICATE &REST SB-IMPL::ARGS &KEY
                SB-IMPL::KEY)
  Declared type: (FUNCTION
                  (SEQUENCE (OR FUNCTION SYMBOL) &REST T &KEY
                   (:KEY (OR FUNCTION SYMBOL)))
                  (VALUES SEQUENCE &OPTIONAL))
  Documentation:
    Destructively sort SEQUENCE. PREDICATE should return non-NIL if
       ARG1 is to precede ARG2.
  Inline proclamation: MAYBE-INLINE (inline expansion available)

It mentions two arguments to the compare function. And indeed, we have an example here with the lambda function: http://www.lispworks.com/documentation/HyperSpec/Body/f_sort_.htm

 (setq tester (copy-seq "lkjashd")) =>  "lkjashd"
 (stable-sort tester #'(lambda (x y) (and (oddp x) (evenp y))))

Your function must take two arguments, tree-1 and tree-2.

Compare them with (> (tree-node-freq tree-1) (tree-node-freq tree-2)).

Last bits

(nil)

Your are calling the "nil" function. Just return nil, as you return T.

Better yet, use when. If when is false, the function implicitly returns nil.

(sort list compare)

You must reference compare as being a function: #'compare. See https://lispcookbook.github.io/cl-cookbook/functions.html#referencing-functions-by-name-single-quote--or-sharpsign-quote-