在lisp中对由手动结构组成的列表进行排序

Question

我的代码中有一个结构

(defstruct tree-node char freq )

我有一个这些"节点"的列表。例如(#\a 4，#b 5，#q 17(，我想按降序对它们进行排序。如何使用排序函数。我已经写了一个比较函数，但我不知道这是否是一种方法。

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

当我调用排序函数时

(sort list compare)

它说比较函数没有价值。顺便说一句，我是口齿不清的新手，所以请不要评判：(

Answer 1

sort函数需要一个接受两个参数并返回一个广义布尔值的谓词函数，而OP代码显示一个不接受参数的comparison函数。当比较本身返回所需的布尔值时，没有理由使用if。还要注意，访问sort表达式中的函数需要尖引号，即(sort list #'compare)而不是(sort list compare)。

您可以将比较函数写成：

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

你也可以用一个匿名函数来做这件事：

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

但是，最好利用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

如果您在REPL中定义compare函数，我们会看到警告：

(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

你把>的右括号放得太远了。而不是> a b，我们只得到了> (a) b c。所以if既没有then子句，也没有else子句。

您可能想要使用带有lisp缩进的编辑器。

比较

查看sort的文档：

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)

它提到了compare函数的两个参数。实际上，我们这里有一个lambda函数的例子：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))))

函数必须包含两个参数tree-1和tree-2。

与CCD_ 17进行比较。

最后一位

(nil)

您正在呼叫"；nil"；作用只需返回nil，就像返回T一样。

更好的是，使用when。如果when为false，则函数隐式返回nil。

(sort list compare)

必须将compare引用为函数：#'compare。看见https://lispcookbook.github.io/cl-cookbook/functions.html#referencing-按名称的函数单引号或锐符号引号-