Search code examples
functional-programminglispcommon-lispclisp

Sorting a list made out of manual structures in lisp

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 :)

Solution

  • 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))