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

Question

我的代码中有一个结构

(defstruct tree-node char freq )

我有这些 'nodes' 的列表。例如 (#\a 4, #b 5, #q 17) 我想按降序对它们进行排序。我怎样才能使用排序功能。我已经写了一个比较函数，但我不知道这是否是一种方法。

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

当我调用排序函数时

(sort list compare)

它说比较功能没有价值。顺便说一句，我是 lisp 的新手，所以请不要评判 :)

Answer 1

如果您在 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)

它提到了比较函数的两个参数。事实上，我们这里有一个 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。

将它们与 (> (tree-node-freq tree-1) (tree-node-freq tree-2)) 进行比较。

最后一点

(nil)

您正在调用“nil”函数。只是 return nil，正如你 return T.

更好的是，使用 when。如果 when 为 false，函数隐式 returns nil.

(sort list compare)

您必须将 compare 作为函数引用：#'compare。参见 https://lispcookbook.github.io/cl-cookbook/functions.html#referencing-functions-by-name-single-quote--or-sharpsign-quote-

Answer 2

sort 函数需要一个带有两个参数的谓词函数和 returns 一个广义布尔值，而 OP 代码显示了一个不带参数的 comparison 函数。当比较本身 returns 所需的布尔值时，没有理由使用 if。另请注意，需要 sharp-quote 才能访问 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))

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

Sorting a list made out of manual structures in lisp

lisp

clisp

functional-programming

common-lisp

比较

最后一点